记录编号	568228	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	EYOI的成立	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.416 s
提交时间	2021-12-20 20:11:31	内存使用	5.81 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=100000+5;
int n;
int a[N]={0},b[N]={0};
int p[2*N]={0};
int lowbit(int x){
    return x&(-x);
}
void add(int x,int y){
    int t=x;
    for (int i=x;i<=200000;i+=lowbit(i)){
        p[i]=max(p[i],t);
    }
    return ;
}
int getsum(int x){
    int t=0;
    for (int i=x;i>0;i-=lowbit(i)){
        t=max(t,p[i]);
    }
    return t;
}
int main(){
    freopen ("EYOI_found.in","r",stdin);
    freopen ("EYOI_found.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    for (int i=1;i<=n;i++){
        int t=getsum(a[i]+b[i]-1);
        printf ("%d ",t); 
        if (a[i]>0) add(a[i],1);
    }
    return 0;
}