Submission #1227889
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define NN 100400 long long oo; struct node{ long long l,r; long long max,min; long long sum; long long fg; }tree[NN*4]; long long n,q; void Init(long long l,long long r,long long idd){ tree[idd].l=l; tree[idd].r=r; tree[idd].max=tree[idd].min=0; tree[idd].sum=0; tree[idd].fg=0; if(r-l<=1) return ; long long mid=(l+r)/2; Init(l,mid,idd<<1); Init(mid,r,idd<<1|1); } void Up(long long idd){ tree[idd].sum=tree[idd<<1].sum+tree[idd<<1|1].sum; tree[idd].max=max(tree[idd<<1].max,tree[idd<<1|1].max); tree[idd].min=min(tree[idd<<1].min,tree[idd<<1|1].min); } void Down(long long idd){ if(tree[idd].fg){ tree[idd<<1].fg=tree[idd<<1|1].fg=1; tree[idd<<1].min=tree[idd<<1|1].min=tree[idd].min; tree[idd<<1].max=tree[idd<<1|1].max=tree[idd].max; tree[idd<<1].sum=tree[idd].min*(tree[idd<<1].r-tree[idd<<1].l); tree[idd<<1|1].sum=tree[idd].min*(tree[idd<<1|1].r-tree[idd<<1|1].l); tree[idd].fg=0; } } long long u; long long bg; long long ssum; long long ftt; void Date(long long l,long long r,long long rr,long long num,long long pre,long long idd){ long long ssum=num+tree[idd].sum+ftt; long long avg=ssum/(rr-l); if(ssum-avg*(rr-l)) avg++; if(avg>pre) return ; if(u==-1&&tree[idd].max<=avg) u=avg,bg=l; else if(u>=avg&&tree[idd].max<=avg)u=avg,bg=l; // printf("~%d %d %d %lld %lld %lld\n",l,r,bg,u,ssum,pre); if(r-l<=1) return ; Down(idd); long long mid=(l+r)/2; if(tree[idd<<1].min*(rr-tree[idd<<1|1].l)>=tree[idd<<1|1].sum+num) Date(mid,r,rr,num,tree[idd<<1].min,idd<<1|1); else { ftt+=tree[idd<<1|1].sum; Date(l,mid,rr,num,pre,idd<<1); } Up(idd); } void Update(long long l,long long r,long long rr,long long num,long long pre,long long idd){ if(tree[idd].l==l&&tree[idd].r==r){ Date(l,r,rr,num,pre,idd); ftt+=tree[idd].sum; return; } Down(idd); long long mid=(tree[idd].l+tree[idd].r)/2; if(mid>=r) Update(l,r,rr,num,pre,idd<<1); else if(mid<=l) Update(l,r,rr,num,tree[idd<<1].min,idd<<1|1); else{ Update(mid,r,rr,num,tree[idd<<1].min,idd<<1|1); Update(l,mid,rr,num,pre,idd<<1); } Up(idd); } void Query(long long l,long long r,long long idd){ if(tree[idd].l==l&&tree[idd].r==r){ ssum+=tree[idd].sum; return; } Down(idd); long long mid=(tree[idd].l+tree[idd].r)/2; if(mid>=r) Query(l,r,idd<<1); else if(mid<=l) Query(l,r,idd<<1|1); else{ Query(l,mid,idd<<1); Query(mid,r,idd<<1|1); } Up(idd); } void fugai(long long l,long long r,long long shu,long long idd){ if(tree[idd].l==l&&tree[idd].r==r){ tree[idd].max=tree[idd].min=shu; tree[idd].sum=(r-l)*shu; tree[idd].fg=1; return; } Down(idd); long long mid=(tree[idd].l+tree[idd].r)/2; if(mid>=r) fugai(l,r,shu,idd<<1); else if(mid<=l) fugai(l,r,shu,idd<<1|1); else{ fugai(l,mid,shu,idd<<1); fugai(mid,r,shu,idd<<1|1); } Up(idd); } void Print(long long l,long long r,long long idd){ if(r-l<=1) { printf("%lld\n",tree[idd].sum); return; } Down(idd); long long mid=(r+l)/2; Print(l,mid,idd<<1); Print(mid,r,idd<<1|1); Up(idd); } int main(){ oo=1LL*2000000*10000000+10; scanf("%lld%lld",&n,&q); Init(1,n+1,1); for(long long i=1;i<=q;i++){ long long x;long long y; scanf("%lld%lld",&x,&y); u=-1;bg=-1; ftt=0; Update(1,x+1,x+1,y,oo,1); ssum=0; Query(bg,x+1,1); long long num=(x+1)-bg; long long sum=ssum+y; long long avg=sum/num; long long a1=sum-avg*num; if(a1){ fugai(bg,bg+a1,avg+1,1); } fugai(bg+a1,x+1,avg,1); // Print(1,n+1,1); } Print(1,n+1,1); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Sushi |
User | yingpingan |
Language | C++14 (Clang 3.8.0) |
Score | 0 |
Code Size | 3672 Byte |
Status | CE |
Compile Error
./Main.cpp:1:9: fatal error: 'bits/stdc++.h' file not found #include<bits/stdc++.h> ^ 1 error generated.