Hi, Tried solving **[MKTHNUM — K-th Number](http://www.spoj.com/problems/MKTHNUM/)** 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](http://spojtoolkit.com/test/MKTHNUM) 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. :)**
↵
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. :)**
