Submission #143752

#	Time	Username	Problem	Language	Result	Execution time	Memory
143752		sjimed	즐거운 사진 수집 (JOI13_collecting)	C++14	100 / 100	1245 ms	62360 KiB

collecting

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70