Submission #12974

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

collecting

#include<stdio.h>
typedef long long ll;
int gap,r,t,n,q,cnt[2][21],pos[5000010],sw,tree[2][5000010];
ll dap[21],arr[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]==arr[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]==arr[pos[k]]){
        if(pos[k]==1) cnt[p][pos[k*2]]--;
        cnt[p][pos[k*2]]--;
        sw=1;
        r=k;
    }
}
void pro()
{
    int i;
    ll sum=0,ans=0;
    for(i=n;i>=0;i--){
        sum+=arr[i]*ll(cnt[0][i]);
        dap[i]=sum/arr[i]*ll(cnt[1][i]);
    }
    sum=0;
    for(i=n;i>=0;i--){
        dap[i]+=sum/arr[i]*ll(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("%lld\n",ans);
}
int main()
{
    int i,j,x,p,w=1,c=0;
    scanf("%d %d",&n,&q); t=1<<n;
    for(i=0;i<=20;i++) arr[i]=1<<i;
    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: 70 / 70