代码

#include <cstdio>

#include <vector>

using namespace std;

typedef long long ll;

struct Modify {
    int qid, x;

    Modify() {}

    Modify(int qid, int x) : qid(qid), x(x) {}
};

const int N = 300010, FW = 1 << 21;

int n, m, q;
int qCnt;
int qx[N], qy[N];
int ind[N * 2];
int fw[FW];
vector<Modify> mr[N], mc;
vector<ll> rr[N], rc;

int rmv(int k);
void change(int k);
int lowBit(int k);

int main() {
    for (int i = 1; i < FW; ++i)
        fw[i] = lowBit(i);
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= q; ++i) {
        scanf("%d%d", &qx[i], &qy[i]);
        if (qy[i] == m)
            mc.push_back(Modify(++qCnt, qx[i]));
        else {
            mr[qx[i]].push_back(Modify(++qCnt, qy[i]));
            mc.push_back(Modify(++qCnt, qx[i]));
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < mr[i].size(); ++j) {
            ind[mr[i][j].qid] = rmv(mr[i][j].x);
        }
        for (int j = 0; j < mr[i].size(); ++j)
            change(ind[mr[i][j].qid]);
    }
    for (int j = 0; j < mc.size(); ++j)
        ind[mc[j].qid] = rmv(mc[j].x);
    qCnt = 0;
    for (int i = 1; i <= q; ++i) {
        ll v;
        if (qy[i] == m) {
            ++qCnt;
            if (ind[qCnt] <= n)
                v = ind[qCnt] * (ll)m;
            else
                v = rc[ind[qCnt] - n - 1];
            rc.push_back(v);
            printf("%lld\n", v);
        } else {
            ++qCnt;
            if (ind[qCnt] < m)
                v = ind[qCnt] + (qx[i] - 1) * (ll)m;
            else
                v = rr[qx[i]][ind[qCnt] - m];
            printf("%lld\n", v);
            rc.push_back(v);
            ++qCnt;
            if (ind[qCnt] <= n)
                v = ind[qCnt] * (ll)m;
            else
                v = rc[ind[qCnt] - n - 1];
            rr[qx[i]].push_back(v);
        }
    }
    return 0;
}

int lowBit(int k) {
    return k & -k;
}

void change(int k) {
    for (; k < FW; k += lowBit(k))
        ++fw[k];
}

int rmv(int k) {
    int ret = 0;
    --k;
    for (int l = 20; l >= 0; --l)
        if (fw[ret | (1 << l)] <= k)
            k -= fw[ret |= (1 << l)];
    ++ret;
    for (k = ret; k < FW; k += lowBit(k))
        --fw[k];
    return ret;
}

评测结果