NOIP2017 phalanx2

#include <cstdio>
#include <cstdlib>

#define LOG(FMT...) // fprintf(stderr, FMT)

using namespace std;

typedef long long ll;

struct node {
    int l, r, sum;
    ll d;
    node *ls, *rs;
};

struct que {
    int step, sz, used;
    ll fst;
    node* root;

    ll get(int rk);
    void put(ll x);
};

const int N = 300010;

int n, m, q;
que q1[N], q2;

node* create(int l, int r, int sum, ll d);

int main() {
//  freopen("test.out", "w", stdout);
    int x, y;
    ll i1, i2;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        q1[i].sz = q1[i].used = m - 1;
        q1[i].step = 1;
        q1[i].fst = (ll)(i - 1) * m;
        q1[i].root = create(1, q1[i].sz + q, q1[i].sz, 0);
        q1[i].root->ls = create(1, q1[i].sz, q1[i].sz, 0);
        q1[i].root->rs = create(m, q1[i].sz + q, 0, 0);
    }
    q2.sz = q2.used = n;
    q2.step = m;
    q2.fst = 0;
    q2.root = create(1, n + q, n, 0);
    q2.root->ls = create(1, n, n, 0);
    q2.root->rs = create(n + 1, n + q, 0, 0);
    while (q--) {
        scanf("%d%d", &x, &y);
        if (y == m) {
            i1 = q2.get(x);
            q2.put(i1);
            printf("%lld\n", i1);
        } else {
            i1 = q1[x].get(y);
            i2 = q2.get(x);
            q1[x].put(i2);
            q2.put(i1);
            printf("%lld\n", i1);
        }
        LOG("%d\n", q);
    }
    return 0;
}

inline node* create(int l, int r, int sum, ll d) {
    static node pool[N << 5];
    static node* p = pool;
    ++p;
    p->l = l;
    p->r = r;
    p->sum = sum;
    LOG("%d %d\n", l, r);
    LOG("%d\n", sum);
    p->d = d;
    return p;
}

ll que::get(int rk) {
    node* p = root;
    while (p->l != p->r) {
        LOG("%d %d %d\n", p->l, p->r, rk);
        --p->sum;
        if (!p->ls) {
            int mid = (p->l + p->r) >> 1;
            p->ls = create(p->l, mid, mid - p->l + 1, 0);
            p->rs = create(mid + 1, p->r, p->r - mid, 0);
        }
        LOG("%d %d\n", p->ls->l, p->ls->r);
        if (rk <= p->ls->sum)
            p = p->ls;
        else {
            rk -= p->ls->sum;
            p = p->rs;
        }
    }
    p->sum = 0;
    if (p->l <= sz)
        return (ll)step * p->l + fst;
    return p->d;
}

void que::put(ll x) {
    node* p = root;
    ++used;
    while (p->l != p->r) {
        ++p->sum;
        if (!p->ls) {
            int mid = (p->l + p->r) >> 1;
            p->ls = create(p->l, mid, 0, 0);
            p->rs = create(mid + 1, p->r, 0, 0);
        }
        if (p->ls->r >= used)
            p = p->ls;
        else
            p = p->rs;
    }
    p->sum = 1;
    p->d = x;
}