#include<stdio.h>
int r,t,n,q,cnt[2][21],pos[3000010],sw,dap[21],tree[2][3000010],hap[21];
int update(int p,int s,int x,int y,int k)
{
if(x==y)
{
if(tree[p][k]==0){tree[p][k]=1; return 1;}
else{tree[p][k]=0; return -1;}
}
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) tree[p][k]=tree[p][k]+update(p,s,x,(x+y)/2,k*2);
else tree[p][k]=tree[p][k]+update(p,s,(x+y)/2+1,y,k*2+1);
if(tree[p][k]==0)
{
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
36244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
