Submission #12973

#TimeUsernameProblemLanguageResultExecution timeMemory
12973dohyun0324즐거운 사진 수집 (JOI13_collecting)C++98
30 / 100
2920 ms59680 KiB
#include<stdio.h> int gap,r,t,n,q,cnt[2][21],pos[5000010],sw,dap[21],tree[2][5000010],hap[21]; void update(int p,int s,int x,int y,int k) { if(x==y){ if(tree[p][k]==0) tree[p][k]=1, gap=1; else tree[p][k]=0, gap=-1; return; } if(tree[p][k]==0 || tree[p][k]==1<<pos[k]) cnt[p][pos[k]]--, cnt[p][pos[k*2]]+=2; if(s<=(x+y)/2) update(p,s,x,(x+y)/2,k*2); else update(p,s,(x+y)/2+1,y,k*2+1); tree[p][k]=tree[p][k]+gap; if(tree[p][k]==0 || tree[p][k]==1<<pos[k]){ if(pos[k]==1) cnt[p][pos[k*2]]--; cnt[p][pos[k*2]]--; sw=1; r=k; } } void pro() { int i,sum=0,ans=0; for(i=n;i>=0;i--){ sum+=(1<<i)*cnt[0][i]; dap[i]=sum/(1<<i)*cnt[1][i]; } sum=0; for(i=n;i>=0;i--){ dap[i]+=sum/(1<<i)*cnt[0][i]; sum+=(1<<i)*cnt[1][i]; } for(i=0;i<=n;i++) ans+=dap[i]; for(i=0;i<=n;i++){ dap[i]/=4; ans+=dap[i]; dap[i+1]+=dap[i]; } printf("%d\n",ans); } int main() { int i,j,x,p,w=1,c=0; scanf("%d %d",&n,&q); t=1<<n; for(i=1;i<=t*2;i++){ c++; for(j=i;j<=i+w-1;j++) pos[j]=n-c+1; i=j-1; w*=2; } cnt[0][pos[1]]=cnt[1][pos[1]]=1; for(i=1;i<=q;i++){ scanf("%d %d",&p,&x); sw=0; r=0; update(p,x,1,t,1); if(r) cnt[p][pos[r]]++; pro(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...