Submission #223261

#	Time	Username	Problem	Language	Result	Execution time	Memory
223261		shenxy	Klasika (COCI20_klasika)	C++11	110 / 110	3642 ms	477696 KiB

klasika

#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 (stderr)

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 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44