oj.uz

Submission #142622

# Submission time Handle Problem Language Result Execution time Memory
142622 2019-08-10T04:37:05 Z gs18103 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 1364 ms 78268 KB 
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false); cin.tie(0)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back
#define fi first
#define se second
#define INF 2000000000
#define LINF 1000000000000000000LL

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

void update(auto &tree, auto &cnt, int x, int n) {
	x += (1 << n) - 1;
	tree[x] = (tree[x] + 1) % 2;
	for(int i = n - 1; i >= 0; i--) {
		x >>= 1;
		if(tree[x] == (1 << (n-i)) || tree[x] == 0) cnt[i]++;
		tree[x] = tree[x*2] + tree[x*2+1];
		if(tree[x] == (1 << (n-i)) || tree[x] == 0) cnt[i]--;
	}
}

int main() {
	fastio;
	vector <ll> treex, treey, cntx, cnty;
	int n, q;
	cin >> n >> q;
	treex.resize((1<<(n+1))+10);
	treey.resize((1<<(n+1))+10);
	cntx.resize(n+10);
	cnty.resize(n+10);

	while(q--) {
		int t, x;
		cin >> t >> x;
		if(t) update(treex, cntx, x, n);
		else update(treey, cnty, x, n);
		ll ans = 0;
		for(int i = 0; i < n; i++) {
			ans += (1LL<<i) * (cntx[i] + cnty[i]) - cntx[i] * cnty[i];
		}
		cout << ans * 4 + 1 << '\n';
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1339 ms 60476 KB Output is correct
2 Correct 1346 ms 78180 KB Output is correct
3 Correct 1211 ms 58944 KB Output is correct
4 Correct 1338 ms 78268 KB Output is correct
5 Correct 1334 ms 77848 KB Output is correct
6 Correct 1317 ms 76788 KB Output is correct
7 Correct 1364 ms 77920 KB Output is correct
8 Correct 1348 ms 78236 KB Output is correct
9 Correct 1215 ms 57504 KB Output is correct
10 Correct 1251 ms 60024 KB Output is correct
11 Correct 1315 ms 76756 KB Output is correct
12 Correct 1326 ms 76752 KB Output is correct
13 Correct 1223 ms 59804 KB Output is correct