Submission #787326

#	Time	Username	Problem	Language	Result	Execution time	Memory
787326		qwerasdfzxcl	즐거운 사진 수집 (JOI13_collecting)	C++17	100 / 100	873 ms	44732 KiB

collecting

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int cntR[21][2], cntC[21][2], onR[1<<21], onC[1<<21], R[21][1<<21], C[21][1<<21];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;

	ll ans = 1;
	for (int i=1;i<=n;i++){
		cntR[i][0] = 1<<(n-i);
		cntC[i][0] = 1<<(n-i);
	}

	// int sz = 1<<n;

	while(q--){
		int op, x;
		// scanf("%d %d", &op, &x);
		cin >> op >> x;
		--x;

		if (op==0){
			onR[x] ^= 1;
			for (int i=1;i<=n;i++){
				int &cnt = R[i][x>>i];
				if (cnt==0){
					ans += (4LL) * cntC[i][0];
					cntR[i][0]--;
				} 
				else if (cnt==(1<<i)){
					ans += (4LL) * cntC[i][0];
					cntR[i][0]--;
				}

				if (onR[x]==1) cnt++;
				else cnt--;

				// printf("ok cnt = %d\n", cnt);

				if (cnt==0){
					ans -= (4LL) * cntC[i][0];
					cntR[i][0]++;
				}
				else if (cnt==(1<<i)){
					ans -= (4LL) * cntC[i][0];
					cntR[i][0]++;
				} 
			}
		}

		else{
			onC[x] ^= 1;

			for (int i=1;i<=n;i++){
				int &cnt = C[i][x>>i];
				if (cnt==0){
					ans += (4LL) * cntR[i][0];
					cntC[i][0]--;
				} 
				else if (cnt==(1<<i)){
					ans += (4LL) * cntR[i][0];
					cntC[i][0]--;
				}

				if (onC[x]==1) cnt++;
				else cnt--;

				if (cnt==0){
					ans -= (4LL) * cntR[i][0];
					cntC[i][0]++;
				} 
				else if (cnt==(1<<i)){
					ans -= (4LL) * cntR[i][0];
					cntC[i][0]++;
				} 
			}
		}

		printf("%lld\n", ans);
	}
}

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