Submission #12972

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

collecting

#include<stdio.h>
int gap,r,t,n,q,cnt[2][21],pos[3000010],sw,dap[21],tree[2][3000010],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;
}

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