oj.uz

Submission #223261

# Submission time Handle Problem Language Result Execution time Memory
223261 2020-04-15T06:26:20 Z shenxy Klasika (COCI20_klasika) C++11
110 / 110
 3642 ms 477696 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;
typedef pair<unsigned, unsigned> ii;
typedef pair<string, ii> query;
unsigned N = 1, parent[200001], xroot[200001], preo[500000], eran[500000], cnt = -1;
vector<unsigned> children[200001];
void dfs(int v) {
	preo[v] = ++cnt;
	for (int i: children[v]) dfs(i);
	eran[v] = cnt;
}
struct seg {
	unsigned s, e, m;
	set<unsigned> v;
	seg *l, *r;
	seg(unsigned _s, unsigned _e) {
		s = _s, e = _e, m = (s + e) >> 1;
		l = r = NULL;
	}
	void update(unsigned i, unsigned nv) {
		if (s != e) {
			if (i > m) {
				if (r == NULL) r = new seg(m + 1, e);
				r -> update(i, nv);
			} else {
				if (l == NULL) l = new seg(s, m);
				l -> update(i, nv);
			}
			v.insert(nv);
		} else v.insert(nv);
	}
	unsigned query(unsigned a, unsigned b, unsigned x) {
		if (s == e) return 0;
		int range = (e - s + 1) >> 1;
		if (x & range) {
			if (l != NULL && l -> v.lower_bound(a) != l -> v.upper_bound(b)) return range + l -> query(a, b, x & (range - 1));
			else return r -> query(a, b, x & (range - 1));
		} else {
			if (r != NULL && r -> v.lower_bound(a) != r -> v.upper_bound(b)) return range + r -> query(a, b, x & (range - 1));
			else return l -> query(a, b, x & (range - 1));
		}
	}
} *root = new seg(0, (1U << 31) - 1);
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	unsigned Q, x, y;
	cin >> Q;
	string op;
	query queries[Q];
	xroot[0] = 0;
	for (int i = 0; i < Q; ++i) {
		cin >> op >> x >> y;
		queries[i] = query(op, ii(x, y));
		if (op[0] == 'A') {
			children[x - 1].push_back(N);
			parent[N] = x - 1;
			xroot[N] = xroot[x - 1] ^ y;
			++N;
		}
	}
	dfs(0);
	N = 1;
	root -> update(0, 0);
	for (int i = 0; i < Q; ++i) {
		if (queries[i].first[0] == 'A') {
			root -> update(xroot[N], preo[N]);
			++N;
		} else cout << root -> query(preo[queries[i].second.second - 1], eran[queries[i].second.second - 1], xroot[queries[i].second.first - 1]) << endl;
	}
	return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Q; ++i) {
                  ~~^~~
klasika.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Q; ++i) {
                  ~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5248 KB Output is correct
2 Correct 8 ms 5376 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 8 ms 5224 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5504 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5504 KB Output is correct
11 Correct 8 ms 5632 KB Output is correct
12 Correct 8 ms 5632 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5248 KB Output is correct
2 Correct 8 ms 5376 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 8 ms 5224 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5504 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5504 KB Output is correct
11 Correct 8 ms 5632 KB Output is correct
12 Correct 8 ms 5632 KB Output is correct
13 Correct 15 ms 6784 KB Output is correct
14 Correct 16 ms 8192 KB Output is correct
15 Correct 17 ms 9600 KB Output is correct
16 Correct 18 ms 10880 KB Output is correct
17 Correct 15 ms 6656 KB Output is correct
18 Correct 21 ms 8064 KB Output is correct
19 Correct 17 ms 9472 KB Output is correct
20 Correct 19 ms 10752 KB Output is correct
21 Correct 15 ms 6656 KB Output is correct
22 Correct 16 ms 8064 KB Output is correct
23 Correct 17 ms 9472 KB Output is correct
24 Correct 20 ms 10752 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1610 ms 137084 KB Output is correct
2 Correct 2155 ms 255572 KB Output is correct
3 Correct 2608 ms 366120 KB Output is correct
4 Correct 3032 ms 477192 KB Output is correct
5 Correct 1400 ms 138104 KB Output is correct
6 Correct 2053 ms 252200 KB Output is correct
7 Correct 2714 ms 361804 KB Output is correct
8 Correct 3132 ms 470688 KB Output is correct
9 Correct 1488 ms 137828 KB Output is correct
10 Correct 2103 ms 253092 KB Output is correct
11 Correct 2600 ms 364116 KB Output is correct
12 Correct 3021 ms 472492 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5248 KB Output is correct
2 Correct 8 ms 5376 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 8 ms 5224 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5504 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Correct 8 ms 5248 KB Output is correct
10 Correct 8 ms 5504 KB Output is correct
11 Correct 8 ms 5632 KB Output is correct
12 Correct 8 ms 5632 KB Output is correct
13 Correct 15 ms 6784 KB Output is correct
14 Correct 16 ms 8192 KB Output is correct
15 Correct 17 ms 9600 KB Output is correct
16 Correct 18 ms 10880 KB Output is correct
17 Correct 15 ms 6656 KB Output is correct
18 Correct 21 ms 8064 KB Output is correct
19 Correct 17 ms 9472 KB Output is correct
20 Correct 19 ms 10752 KB Output is correct
21 Correct 15 ms 6656 KB Output is correct
22 Correct 16 ms 8064 KB Output is correct
23 Correct 17 ms 9472 KB Output is correct
24 Correct 20 ms 10752 KB Output is correct
25 Correct 1610 ms 137084 KB Output is correct
26 Correct 2155 ms 255572 KB Output is correct
27 Correct 2608 ms 366120 KB Output is correct
28 Correct 3032 ms 477192 KB Output is correct
29 Correct 1400 ms 138104 KB Output is correct
30 Correct 2053 ms 252200 KB Output is correct
31 Correct 2714 ms 361804 KB Output is correct
32 Correct 3132 ms 470688 KB Output is correct
33 Correct 1488 ms 137828 KB Output is correct
34 Correct 2103 ms 253092 KB Output is correct
35 Correct 2600 ms 364116 KB Output is correct
36 Correct 3021 ms 472492 KB Output is correct
37 Correct 2219 ms 140792 KB Output is correct
38 Correct 2766 ms 255412 KB Output is correct
39 Correct 3184 ms 369104 KB Output is correct
40 Correct 3184 ms 477696 KB Output is correct
41 Correct 2390 ms 138488 KB Output is correct
42 Correct 3017 ms 252120 KB Output is correct
43 Correct 3279 ms 361620 KB Output is correct
44 Correct 3417 ms 469792 KB Output is correct
45 Correct 2498 ms 138108 KB Output is correct
46 Correct 3111 ms 253176 KB Output is correct
47 Correct 3568 ms 362392 KB Output is correct
48 Correct 3642 ms 472432 KB Output is correct