Submission #163201

#	Time	Username	Problem	Language	Result	Execution time	Memory
163201		TadijaSebez	즐거운 사진 수집 (JOI13_collecting)	C++11	100 / 100	1593 ms	70520 KiB

collecting

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=(1<<20);
const int L=21;
int n;
struct Solve1D
{
	int sum[L][N],state[N],cnt[L];
	Solve1D(){}
	void init()
	{
		for(int i=0;i<=n;i++) cnt[i]=1<<(n-i);
	}
	void Change(int x)
	{
		for(int i=0;i<=n;i++)
		{
			int sz=1<<i;
			int block=x/sz;
			if(sum[i][block]==0 || sum[i][block]==sz) cnt[i]--;
			if(state[x]==1) sum[i][block]--;
			else sum[i][block]++;
			if(sum[i][block]==0 || sum[i][block]==sz) cnt[i]++;
		}
		state[x]^=1;
	}
} R,C;
int main()
{
	int q;
	scanf("%i %i",&n,&q);
	ll sum=0;
	for(int i=0;i<=n;i++) sum+=(ll)(1<<i)*(1<<i);
	R.init();C.init();
	while(q--)
	{
		int t,x;
		scanf("%i %i",&t,&x);
		x--;
		if(t==0) R.Change(x);
		else C.Change(x);
		ll ans=sum;
		for(int i=1;i<=n;i++) ans-=(ll)4*R.cnt[i]*C.cnt[i];
		printf("%lld\n",ans);
	}
	return 0;
}

Compilation message (stderr)

collecting.cpp: In function 'int main()':
collecting.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
collecting.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&t,&x);
   ~~~~~^~~~~~~~~~~~~~~

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