SPOJ — MKTHNUM using MO's algorithm
Difference between en1 and en2, changed 21 character(s)
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. :)**

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Pranky 2016-08-02 19:53:42 21
en1 English Pranky 2016-08-02 19:39:56 3556 Initial revision (published)