记录编号	562680	评测结果	AAAAAAAAAA
题目名称	[POJ 2828]排队买票	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2021-07-09 09:38:05	内存使用	1.00 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 200005;
int n;
int pos[maxn],val[maxn];
int ans[maxn];
int lowbit(int x) {
    return x & -x;
}
int c[maxn];
void build() {
    for(int i = 1;i <= 2e5;++ i) {
        c[i] = lowbit(i);
    }
    return ;
}
void update(int x,int k) {
    for(;x <= n;x += lowbit(x)) {
        c[x] += k;
    }
    return ;
}
int query(int k,int val) {
    int sum = 0,cnt = 0;
    for(int p = 1 << 17;p;p >>= 1) {
        if(sum + p <= n&&cnt + c[sum + p] <= k) {
            sum += p;
            cnt += c[sum];
        }
    }
    ans[sum + 1] = val;
    return sum + 1;
}
int main() {
    freopen("buytickets.in","r",stdin);
    freopen("buytickets.out","w",stdout);
    while(~ scanf("%d",&n)) {
        for(int i = 1;i <= n;++ i) {
            scanf("%d%d",&pos[i],&val[i]);
        }
        build();
        for(int i = n;i;-- i) {
            int t = query(pos[i] , val[i]);
            update(t , -1);
        }
        for(int i = 1;i <= n;++ i) {
            printf("%d ",ans[i]);
        }
        putchar('\n');
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}