SPOJ — MKTHNUM

Revision en1, by Pranky, 2016-08-02 19:39:56

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

Tags spoj.com, mos_algorithm, sqrt-decomposition, mkthnum

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)