代码

#include <sys/auxv.h>
#include <stdint.h>

struct DuckInfo {
  uint64_t abi_version;
  const char *stdin_ptr; uint64_t stdin_size;
  char *stdout_ptr; uint64_t stdout_limit; uint64_t stdout_size;
  char *stderr_ptr; uint64_t stderr_limit; uint64_t stderr_size;
  const char *IB_ptr; uint64_t IB_limit;
  char *OB_ptr; uint64_t OB_limit;
  uint64_t tsc_frequency;
} __attribute__((packed));

#define AT_DUCK 0x6b637564UL

static int X[300005], Y[300005];
static int head[300005], tail[300005], nxt[300005];
static int cnt[300005], off[300005], curpos[300005];
static int flat[300005];
static unsigned char rtype[300005];
static int rref[300005];
static long long rval[300005];
static long long rowval[300005];
static long long ans[300005];
static int bit_row[600005];
static int bit_col[600005];
static long long colvalue[600005];
static int dirty[12000008];

static inline int lb(int x){ return x & (-x); }

static inline int rd(const char*& p){
  int x = 0;
  while (*p < '0' || *p > '9') ++p;
  while (*p >= '0' && *p <= '9') { x = x*10 + (*p - '0'); ++p; }
  return x;
}

static inline void exitasm(){
#ifdef DUCK_RENAME_MAIN
  return;
#else
  __asm__ __volatile__("mov $60, %%rax; xor %%rdi, %%rdi; syscall" ::: "rax","rdi","rcx","r11","memory");
#endif
}

// initial Fenwick value over A[1..Nr] with A[i]=1 for i<=mr, else 0
static inline int iniv(int i, int mr){
  if(i <= mr) return lb(i);
  int lo = i - lb(i);
  return lo < mr ? mr - lo : 0;
}

#ifdef DUCK_RENAME_MAIN
extern "C" int duck_solve()
#else
int main()
#endif
{
  struct DuckInfo *di = (struct DuckInfo *)getauxval(AT_DUCK);
  const char *p = di->stdin_ptr;
  int n = rd(p), m = rd(p), q = rd(p);

  for(int i=0;i<q;i++){
    int x = rd(p), y = rd(p);
    X[i]=x; Y[i]=y;
    if(y < m){
      if(head[x]==0) head[x]=i+1; else nxt[tail[x]]=i+1;
      tail[x]=i+1;
      cnt[x]++;
    }
  }

  // flat array: append order per row (time order within each row)
  off[1]=0;
  for(int x=2;x<=n;x++) off[x]=off[x-1]+cnt[x-1];
  for(int i=0;i<q;i++){
    if(Y[i] < m){
      int x=X[i];
      flat[off[x]+curpos[x]]=i;
      curpos[x]++;
    }
  }

  // ---- per-row offline pass: resolve each event's removed position over the
  // full sequence [real 1..mr] ++ [appended mr+1 ..] ----
  int mr = m-1;
  int Nr = mr + q; // max Fenwick index (appends go up to mr + q_x)
  if(Nr < 1) Nr = 1;
  for(int i=1;i<=Nr;i++) bit_row[i] = iniv(i, mr);
  int highest_row = 1;
  while(highest_row <= Nr) highest_row <<= 1;
  highest_row >>= 1;
  int dc = 0;
  for(int x=1;x<=n;x++){
    for(int j=0;j<dc;j++) bit_row[dirty[j]] = iniv(dirty[j], mr);
    dc = 0;
    int appcnt = 0;
    for(int qid=head[x]; qid; qid=nxt[qid]){
      int i = qid-1;
      int y = Y[i];
      int idx=0, k=y;
      for(int step=highest_row; step; step>>=1){
        int nv=idx+step;
        if(nv <= Nr && bit_row[nv] < k){ idx=nv; k-=bit_row[nv]; }
      }
      int pos = idx+1;
      if(pos <= mr){
        rtype[i]=0;
        rval[i] = (long long)(x-1)*m + pos;
      } else {
        rtype[i]=1;
        rref[i] = pos - mr - 1;
      }
      for(int j=pos; j<=Nr; j+=lb(j)){ bit_row[j]--; dirty[dc++]=j; }
      int ap = mr + 1 + appcnt;
      for(int j=ap; j<=Nr; j+=lb(j)){ bit_row[j]++; dirty[dc++]=j; }
      appcnt++;
    }
  }

  // ---- column structure ----
  int Nc = n + q;
  for(int i=1;i<=Nc;i++) bit_col[i] = (i<=n) ? 1 : 0;
  for(int i=1;i<=Nc;i++){ int j=i+lb(i); if(j<=Nc) bit_col[j]+=bit_col[i]; }
  for(int i=1;i<=n;i++) colvalue[i] = (long long)i * m;
  int highest_col = 1;
  while(highest_col <= Nc) highest_col <<= 1;
  highest_col >>= 1;

  for(int i=0;i<q;i++){
    int x=X[i], y=Y[i];
    int idx=0, k=x;
    for(int step=highest_col; step; step>>=1){
      int nv=idx+step;
      if(nv <= Nc && bit_col[nv] < k){ idx=nv; k-=bit_col[nv]; }
    }
    int pcol = idx+1;
    long long idcol = colvalue[pcol];
    for(int j=pcol; j<=Nc; j+=lb(j)) bit_col[j]--;

    int ap = n+i+1; // append position in column
    if(y==m){
      colvalue[ap] = idcol;
      ans[i] = idcol;
    } else {
      long long idrow;
      if(rtype[i]==0) idrow = rval[i];
      else idrow = rowval[ flat[ off[x] + rref[i] ] ];
      rowval[i] = idcol;
      colvalue[ap] = idrow;
      ans[i] = idrow;
    }
    for(int j=ap; j<=Nc; j+=lb(j)) bit_col[j]++;
  }

  char *o = di->stdout_ptr;
  for(int i=0;i<q;i++){
    long long v = ans[i];
    char tmp[20]; int nn=0;
    do { tmp[nn++] = (char)('0' + (v % 10)); v /= 10; } while(v);
    while(nn) *o++ = tmp[--nn];
    *o++ = '\n';
  }
  di->stdout_size = (uint64_t)(o - di->stdout_ptr);
  exitasm();
  return 0;
}

评测结果