记录编号	476883	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2017]列队	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	2.322 s
提交时间	2017-11-27 16:59:50	内存使用	107.92 MiB

#include <stdio.h>
#include <vector>
#define ls lson[o]
#define rs rson[o]
typedef long long ll;
const int MAXN = 3e5+5;
std::vector<ll> G[MAXN];
int n,m,q,Max,cnt,size[MAXN*30],lson[MAXN*30],rson[MAXN*30],root[MAXN];


char xB[1<<15],*xS=xB,*xTT=xB;
#define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++)
inline int read() {
    int x = 0, f = 1; char ch = getc();
    for (; ch < '0' | ch > '9'; ch = getc()) if (ch == '-') f = -f;
    for (; ch <= '9' && ch >= '0'; ch = getc()) x = x * 10 + (ch ^ 48);
    return x * f;
}

inline void Update(int &o,int l,int r,int x){
    if (!o) o = ++ cnt;
    ++ size[o];
    if (l == r) return;
    register int mid = (l + r) >> 1;
    if (x <= mid) Update(ls,l,mid,x);
    else Update(rs,mid+1,r,x);
}

inline int Query(int o,int l,int r,int k){
    if (l == r) return l;
    register int mid = (l + r) >> 1, tmp = mid - l + 1 - size[ls];
    if (k <= tmp) return Query(ls,l,mid,k);
    else return Query(rs,mid+1,r,k-tmp);
}

inline void Work(){
    register int x = read(),y = read();
    ll Ans;
    if (y == m){
        int now = Query(root[n+1],1,Max,x); Update(root[n+1],1,Max,now);
        printf("%lld\n",Ans = now <= n?1ll*now*m:G[n+1][now-n-1]);
        G[n+1].push_back(Ans);
    }
    else{
        int now = Query(root[x],1,Max,y); Update(root[x],1,Max,now);
        printf("%lld\n",Ans = now < m?1ll*(x-1)*m+now:G[x][now-m]);
        G[n+1].push_back(Ans);
        now = Query(root[n+1],1,Max,x); Update(root[n+1],1,Max,now);
        G[x].push_back(now <= n?1ll*now*m:G[n+1][now-n-1]);
    }
}

int main(){
    freopen("2017phalanx.in","r",stdin);
    freopen("2017phalanx.out","w",stdout);
    n = read(); m = read(); q = read();
    Max = (n>m?n:m) + q;
    while (q --) Work();
    return 0;
}