Submission #12971

#	Time	Username	Problem	Language	Result	Execution time	Memory
12971		dohyun0324	즐거운 사진 수집 (JOI13_collecting)	C++98	0 / 100	0 ms	36244 KiB

collecting

#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70