### Pranky's blog

By Pranky, history, 6 years ago, Hi, Tried solving MKTHNUM — K-th Number Using MO's algorithm. I am getting a WA but I am having a hard time finding a mistake in my code. My code passes a sample test which is offered on the problem site and I tested it using spojtoolkit and things there were looking good.

I would be really happy if a more experienced coder helped me. I think it could be beneficial to the community since I couldn't find an approach using MO's algorithm online to this problem.

Here is my code:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;

#define all(x) x.begin(), x.end()
#define gc getchar_unlocked
#define pc putchar_unlocked
#define pb push_back
#define gdc __gdc
#define endl '\n'
#define Y second
#define X first

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const pii dir_t1[] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const pii dir_t2[] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, 1}};

const ll LLINF = numeric_limits<ll>::max() / 2;
const int INF = 1e9 + 11;
const int MOD = 1e9 + 7;
const int ASCII = 300;

const int MAX_N = 1e5 + 11;
const int MAX_M = 5e3 + 11;
const int BLOCK = ceil(sqrt(MAX_N));
const int MAX_L = ceil(log2(MAX_N));

struct Query {
ll lo, hi, id, k;
inline bool operator < (Query &other) const {
if (lo / BLOCK != other.lo / BLOCK)
return lo / BLOCK < other.lo / BLOCK;
return hi < other.hi;
}
} q[MAX_M];

ll n, m;
ll arr[MAX_N];
ll ans[MAX_M];
ordered_set<ll> dp;

template <typename T> T input() {
T res;
cin >> res;
return res;
}

// FAST I/O
inline void scan_int(ll &x) {
register int c = gc();
int neg = 0;

while ((c < '0' || c > '9') && c != '-')
c = gc();

if (c == '-')
neg = 1, c = gc();

for (x = 0; c >= '0'  && c <= '9'; c = gc())
x = (x << 1 ) + ( x << 3) + c - 48;

if (neg)
x *= -1;
}

inline void print_int(ll x) {
ll rev, exp_10 = 0;
if (x == 0) {
pc('0'), pc('\n');
return;
}

for (rev = x; rev % 10 == 0; rev /= 10)
++exp_10;

for (rev = 0; x; x /= 10)
rev = (rev << 3) + (rev << 1) + x % 10;

while (rev)
pc(rev % 10 + '0'), rev /= 10;
while (exp_10--)
pc('0');
pc('\n');
}

int main() {

scan_int(n), scan_int(m);
for (int i = 0; i < n; ++i)
scan_int(arr[i]);
for (int i = 0; i < m; ++i) {
scan_int(q[i].lo), scan_int(q[i].hi), scan_int(q[i].k);
--q[i].lo, --q[i].hi, --q[i].k, q[i].id = i;
}

sort(q, q + m);
int l = 0, r = 0;
for(int i = 0;  i < m; ++i) {
while(l < q[i].lo)
dp.erase(arr[l++]);
while(l > q[i].lo)
dp.insert(arr[--l]);

while(r <= q[i].hi) {
if (l <= r)
dp.insert(arr[r]);
++r;
}
while(r > q[i].hi + 1)
dp.erase(arr[--r]);

ans[q[i].id] = *dp.find_by_order(q[i].k);
}

for (int i = 0; i < m; ++i)
print_int(ans[i]);

return 0;
}


Thank you for any help in advance. :)  Comments (7)
 » Auto comment: topic has been updated by Pranky (previous revision, new revision, compare).
 » I think you move r incorrectly. ... while(r < q[i].hi) dp.insert(arr[++r]); while(r > q[i].hi) dp.erase(arr[r--]); ... 
 » 6 years ago, # | ← Rev. 2 →   I see that in your printing function you ignore negative numbers, so on test1 1 -100 1 1 1your program will say 100, but it's not a correct answer. Btw, I think that your implementation of Mo's algorithm is OK.PS: I'm not sure that Mo's algorithm with your ordered set will pass time limit.
•  » » 6 years ago, # ^ | ← Rev. 2 →   Tnx 4 the help. :)EDIT: You were right. I fixed the fast I/O for negative numbers and then I got TLE.
•  » » » Perhaps because the Mo algorithm is too slow for this problem. One possible solution to this is Persistent Segment Trees: https://www.youtube.com/watch?v=TH9n_HVkjQM
 »  for(int i = 0; i < m; ++i) { while(l < q[i].lo) dp.erase(arr[l++]); while(l > q[i].lo) dp.insert(arr[--l]); while(r <= q[i].hi) { if (l <= r) dp.insert(arr[r]); ++r; } while(r > q[i].hi + 1) dp.erase(arr[--r]); ans[q[i].id] = *dp.find_by_order(q[i].k); } I guess the order of statements is wrong here. Let us assume current l, r = (2, 3) and new l, r = (10, 20). In first while loop, you delete elements from 2..9. Which means deleting elements that do not exist in set yet. In third while loop, you add elements from 4..29. So the set contains wrong elements. When using MO, I always put insert's first and then remove's.
 » The problem with the erase function is that it erases all occurrences of the number in the set. This would be problematic for test cases like3 2 2 2 3 1 2 1 2 3 1The correct output is 2 2 but your code outputs2 3