oj.uz

Submission #787326

# Submission time Handle Problem Language Result Execution time Memory
787326 2023-07-19T05:19:32 Z qwerasdfzxcl 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 873 ms 44732 KB 
#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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 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 1 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 468 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 798 ms 44448 KB Output is correct
2 Correct 873 ms 44460 KB Output is correct
3 Correct 664 ms 34156 KB Output is correct
4 Correct 816 ms 44732 KB Output is correct
5 Correct 866 ms 44304 KB Output is correct
6 Correct 780 ms 43060 KB Output is correct
7 Correct 768 ms 44380 KB Output is correct
8 Correct 804 ms 44516 KB Output is correct
9 Correct 689 ms 33380 KB Output is correct
10 Correct 691 ms 34832 KB Output is correct
11 Correct 775 ms 43540 KB Output is correct
12 Correct 735 ms 43124 KB Output is correct
13 Correct 697 ms 34896 KB Output is correct