Submission #1187679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187679		JooDdae	즐거운 사진 수집 (JOI13_collecting)	C++20	100 / 100	853 ms	44504 KiB

collecting

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

int n, m, t[2][1 << 22], c[2][20];

void update(int q, int b, int lev = 0, int node = 1, int l = 0, int r = (1 << n)-1) {
	if(b < l || r < b) return;
	if(l == r) {
		t[q][node] = !t[q][node];
		return;
	}
	update(q, b, lev+1, node*2, l, mid), update(q, b, lev+1, node*2+1, mid+1, r);

	c[q][lev] -= t[q][node] == 2;
	t[q][node] = (t[q][node*2] != 2 && t[q][node*2+1] != 2 && t[q][node*2] == t[q][node*2+1] ? t[q][node*2] : 2);
	c[q][lev] += t[q][node] == 2;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;

	while(m--) {
		int q, b; cin >> q >> b;
		update(q, b-1);

		ll ans = 1;
		for(int i=0;i<n;i++) ans += (c[0][i] * (1ll << i) + c[1][i] * ((1ll << i) - c[0][i])) * 4;
		cout << ans << "\n";
	}
}

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