# CK 1603- EDITORIAL

```Just store it in a binary segmented tree and use greedy algorithm technique.

CODE:

#include&#60cstdio>
#include&#60cstring>
#include&#60algorithm>
#include&#60cstdlib>
#define NMAX 300000
#define NN 100000
#define INF 1000000000LL
using namespace std;

typedef long long LL;

struct N{//data to store in tree
LL each,maxsub; //operation load.log update.,subtree statistic(calculate sub tree status in every update)
N(){
each = 0;
maxsub = -INF;
}
};

N st[NMAX];

void update2(int ni,int s,int e,int ps,int pe,LL v){
if(ps > pe)return;
if(pe < s || ps > e)return;
else if(ps <= s && pe >= e){//update all
st[ni].each += v;
}
else{
int mid = (s+e)/2;
update2(ni*2+1,s,mid,ps,min(mid,pe),v);
update2(ni*2+2,mid+1,e,max(mid+1,ps),pe,v);
LL sub1 = st[ni*2+1].each;
LL sub2 = st[ni*2+2].each;
if(mid>s)sub1 += st[ni*2+1].maxsub;
if(mid+1 pe)return -INF;
if(pe < s || ps > e)return -INF;
else if(ps <= s && pe >= e){//get all segment
if(s==e)return st[ni].each;
else return st[ni].maxsub + st[ni].each;
}
else{
int mid = (s+e)/2;
return  max(query2(2*ni+1,s,mid,ps,min(pe,mid)),query2(2*ni+2,mid+1,e,max(ps,mid+1),pe))+st[ni].each;
}
}

int main(){
for(LL i=0;i<=NN;i++){
update2(0,0,NN,i,i,-i);
}
int nn;scanf("%d",&nn);
for(int i=0;i<nn;i++){
int a,b;scanf("%d%d",&a,&b);
update2(0,0,NN,a,NN,b);
LL ret = max(0LL,query2(0,0,NN,0,NN));
printf("%lld\n",ret);
}
return 0;
}```