Submission #787325

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
787325	2023-07-19T05:18:57 Z	박상훈(#10032)	즐거운 사진 수집 (JOI13_collecting)	C++17	100 / 100	886 ms	58820 KB

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	328 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	488 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct

Subtask #3

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	812 ms	44412 KB	Output is correct
2	Correct	817 ms	45240 KB	Output is correct
3	Correct	647 ms	50956 KB	Output is correct
4	Correct	886 ms	49764 KB	Output is correct
5	Correct	852 ms	51884 KB	Output is correct
6	Correct	804 ms	57696 KB	Output is correct
7	Correct	835 ms	58820 KB	Output is correct
8	Correct	857 ms	58700 KB	Output is correct
9	Correct	712 ms	33260 KB	Output is correct
10	Correct	692 ms	39480 KB	Output is correct
11	Correct	811 ms	55780 KB	Output is correct
12	Correct	723 ms	43844 KB	Output is correct
13	Correct	773 ms	37680 KB	Output is correct