oj.uz

Submission #143752

# Submission time Handle Problem Language Result Execution time Memory
143752 2019-08-15T02:58:37 Z sjimed 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1245 ms 62360 KB 
#include<bits/stdc++.h>
using namespace std;

int n, q;
int cntx[21];
int cnty[21];
int sumx[21][1100010];
int sumy[21][1100010];
long long ans = 1;

void update(int t, int x) {
	if(t == 0){
		sumx[0][x] = 1 - sumx[0][x];
		x >>= 1;
		for(int i=1; i<=n; i++) {
			if(sumx[i][x] == 0 || sumx[i][x] == (1 << i)) {
				ans += cnty[i] * 4;
				cntx[i]--;
			}
			sumx[i][x] = sumx[i-1][x*2] + sumx[i-1][x*2+1];
			if(sumx[i][x] == 0 || sumx[i][x] == (1 << i)) {
				ans -= cnty[i] * 4;
				cntx[i]++;
			}
			x >>= 1;
		}
	}

	if(t == 1){
		sumy[0][x] = 1 - sumy[0][x];
		x >>= 1;
		for(int i=1; i<=n; i++) {
			if(sumy[i][x] == 0 || sumy[i][x] == (1 << i)) {
				ans += cntx[i] * 4;
				cnty[i]--;
			}
			sumy[i][x] = sumy[i-1][x*2] + sumy[i-1][x*2+1];
			if(sumy[i][x] == 0 || sumy[i][x] == (1 << i)) {
				ans -= cntx[i] * 4;
				cnty[i]++;
			}
			x >>= 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> q;

	for(int i=0; i<=n; i++) {
		cntx[i] = cnty[i] = 1 << (n-i);

	}

	while(q--) {
		int t, x;
		cin >> t >> x;
		update(t, x-1);

		cout << ans << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 516 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1245 ms 62052 KB Output is correct
2 Correct 1232 ms 61916 KB Output is correct
3 Correct 1110 ms 50968 KB Output is correct
4 Correct 1227 ms 62360 KB Output is correct
5 Correct 1227 ms 61560 KB Output is correct
6 Correct 1180 ms 60724 KB Output is correct
7 Correct 1207 ms 61944 KB Output is correct
8 Correct 1217 ms 61968 KB Output is correct
9 Correct 1100 ms 49556 KB Output is correct
10 Correct 1107 ms 52088 KB Output is correct
11 Correct 1176 ms 60612 KB Output is correct
12 Correct 1212 ms 60648 KB Output is correct
13 Correct 1122 ms 52088 KB Output is correct