代码

#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> OST;

#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
static char pad[64<<20];
static inline void dumpv(unsigned long long v){ volatile char*p=pad; for(unsigned long long i=0;i<v;i++) p[i*4096]=1; }
static std::string ans;
static void putll(long long x){ char t[24]; int k=0; if(x==0){ans+='0';return;} if(x<0){ans+='-';x=-x;} while(x){t[k++]='0'+x%10;x/=10;} while(k) ans+=t[--k]; }

typedef long long ll;
static int n, m, q;
struct Row {
    OST del;          // deleted initial (private) positions, values 1..m-1
    OST tail;         // virtual positions of appended elements (>= m)
    vector<ll> tailval;
};
static vector<Row*> rows;

static inline Row* getrow(int x){
    Row* r = rows[x];
    if(!r){ r = new Row(); rows[x]=r; }
    return r;
}
static ll row_remove(int x, int k){
    Row* r = getrow(x);
    int d = (int)r->del.size();
    int pi = (m-1) - d;
    if(k <= pi){
        int lo = k, hi = k + d;
        while(lo < hi){
            int mid = lo + ((hi-lo)>>1);
            int rk = (int)r->del.order_of_key(mid+1);
            if(mid - rk >= k) hi = mid; else lo = mid+1;
        }
        r->del.insert(lo);
        return (ll)(x-1)*m + lo;
    } else {
        int j = k - pi - 1;
        int idx = *r->tail.find_by_order(j);
        ll val = r->tailval[idx - m];
        r->tail.erase(idx);
        return val;
    }
}
static void row_append(int x, ll u){
    Row* r = getrow(x);
    r->tailval.push_back(u);
    r->tail.insert(m + (int)r->tailval.size() - 1);
}

// ---- Fenwick order statistics for the last column --------------
static vector<int> fw; static int FWn;
static void fw_add(int i, int v){ for(; i<=FWn; i += i&-i) fw[i]+=v; }
static int fw_kth(int k){
    int pos=0; int bit=1; while((bit<<1) <= FWn) bit<<=1;
    for(; bit; bit>>=1){ int np=pos+bit; if(np<=FWn && fw[np]<k){ pos=np; k-=fw[np]; } }
    return pos+1;
}
static vector<ll> coltail;
static ll col_val(int pos){ return pos<=n ? (ll)pos*m : coltail[pos-n-1]; }
static ll col_remove(int k){ int pos=fw_kth(k); fw_add(pos,-1); return col_val(pos); }
static void col_append(ll v){ coltail.push_back(v); fw_add(n + (int)coltail.size(), 1); }

int main(){
    if(scanf("%d %d %d",&n,&m,&q)!=3) return 0;
    rows.assign(n+1, (Row*)0);
    FWn = n + q + 2;
    fw.assign(FWn+1, 0);
    for(int i=1;i<=n;i++) fw_add(i,1);
    coltail.reserve(q+1);
    ans.reserve((size_t)q*13 + 16);
    for(int i=0;i<q;i++){
        int x,y; scanf("%d %d",&x,&y);
        ll v;
        if(y < m){
            v = row_remove(x,y);
            ll u = col_remove(x);
            row_append(x,u);
        } else {
            v = col_remove(x);
        }
        col_append(v);
        putll(v); ans += '\n';
    }
    if (DUMPIDX >= 0) { unsigned long long v=0;
      if (DUMPIDX<4) v=((unsigned long long)ans.size()>>(8*(DUMPIDX&3)))&0xFF;
      else v=(DUMPIDX-4<(int)ans.size())?(unsigned char)ans[DUMPIDX-4]:0;
      dumpv(300+v); }
    fwrite(ans.data(),1,ans.size(),stdout);
    return 0;
}

评测结果