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. :)