Submission #12961

#	Time	Username	Problem	Language	Result	Execution time	Memory
12961		gs13068	즐거운 사진 수집 (JOI13_collecting)	C++98	100 / 100	1528 ms	17472 KiB

collecting

#include<cstdio>

int T[2][2097152];
int d[2][20];

int main()
{
	long long r=0;
    int i,j,k,n,m;
    scanf("%d%d",&n,&m);
    for(i=0;i<2;i++)for(j=1;j<(2<<n);j++)T[i][j]=1;
    for(i=0;i<2;i++)for(j=0;j<n;j++)d[i][j]=1<<j;
    while(m--)
	{
		scanf("%d%d",&i,&j);
		j+=(1<<n)-1;
		T[i][j]=-T[i][j];
		for(k=n-1;j>>=1;k--)
		{
			r+=(long long)d[0][k]*d[1][k];
			d[i][k]-=!!T[i][j];
			T[i][j]=0;
			if(T[i][j<<1]==T[i][(j<<1)+1])T[i][j]=T[i][j<<1];
			d[i][k]+=!!T[i][j];
			r-=(long long)d[0][k]*d[1][k];
		}
        printf("%lld\n",(r<<2)+1);
	}
}

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