oj.uz

Submission #405232

# Submission time Handle Problem Language Result Execution time Memory
405232 2021-05-16T02:16:35 Z ngpin04 Klasika (COCI20_klasika) C++14
33 / 110
 2035 ms 524292 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 2e5 + 5; 
 
int getbit(int x, int i) {
	return (x >> i) & 1;
}

set <int> pos[30 * N];

vector <int> adj[N];
 
pair <int, int> pir[N];
 
int ptr[30 * N][2];
int tin[N];
int val[N];
int tout[N];
int n = 1,q,node,timer;
 
string op[N];

void dfs(int u) {
	tin[u] = ++timer;
	for (int v : adj[u])
		dfs(v);
	tout[u] = timer;
}

void add(int x, int id) {
	int cur = 0;
	for (int i = 29; i >= 0; i--) {
		int &p = ptr[cur][getbit(x, i)];
		if (!p) 
			p = ++node;
		cur = p;
		pos[cur].insert(id);
	}
}

int getmax(int x, int l, int r) {
	int cur = 0;
	int res = 0;	
	for (int i = 29; i >= 0; i--) {
		bool found = false;
		for (int val = 1; val >= 0; val--) {
			int p = ptr[cur][val ^ getbit(x, i)];
			if (!p)
				continue;
			auto it = pos[p].lower_bound(l);
			if (it == pos[p].end() || *it > r)
				continue;
			found = true;
			cur = p;
			res |= (val << i);
			break;
		}	
		if (!found)
			return -1;
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> q;
	for (int i = 1; i <= q; i++) 
		cin >> op[i] >> pir[i].fi >> pir[i].se;
	
	for (int i = 1; i <= q; i++) if (op[i] == "Add") {
		val[++n] = val[pir[i].fi] ^ pir[i].se;
		adj[pir[i].fi].push_back(n);
		pir[i].fi = n;
	}	
 
	dfs(1);

	add(val[1], tin[1]);
	for (int i = 1; i <= q; i++) {
		if (op[i] == "Add")
			add(val[pir[i].fi], tin[pir[i].fi]);
		else {
			int l = tin[pir[i].se];
			int r = tout[pir[i].se];
			cout << getmax(val[pir[i].fi], l, r) << "\n";
		} 

	}
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 293160 KB Output is correct
2 Correct 152 ms 293444 KB Output is correct
3 Correct 150 ms 293244 KB Output is correct
4 Correct 151 ms 293348 KB Output is correct
5 Correct 150 ms 293088 KB Output is correct
6 Correct 149 ms 293104 KB Output is correct
7 Correct 150 ms 293160 KB Output is correct
8 Correct 154 ms 293260 KB Output is correct
9 Correct 165 ms 293100 KB Output is correct
10 Correct 151 ms 293276 KB Output is correct
11 Correct 150 ms 293304 KB Output is correct
12 Correct 148 ms 293284 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 293160 KB Output is correct
2 Correct 152 ms 293444 KB Output is correct
3 Correct 150 ms 293244 KB Output is correct
4 Correct 151 ms 293348 KB Output is correct
5 Correct 150 ms 293088 KB Output is correct
6 Correct 149 ms 293104 KB Output is correct
7 Correct 150 ms 293160 KB Output is correct
8 Correct 154 ms 293260 KB Output is correct
9 Correct 165 ms 293100 KB Output is correct
10 Correct 151 ms 293276 KB Output is correct
11 Correct 150 ms 293304 KB Output is correct
12 Correct 148 ms 293284 KB Output is correct
13 Correct 152 ms 293788 KB Output is correct
14 Correct 149 ms 294400 KB Output is correct
15 Correct 156 ms 295116 KB Output is correct
16 Correct 165 ms 295748 KB Output is correct
17 Correct 151 ms 293692 KB Output is correct
18 Correct 153 ms 294304 KB Output is correct
19 Correct 153 ms 295060 KB Output is correct
20 Correct 153 ms 295572 KB Output is correct
21 Correct 163 ms 293780 KB Output is correct
22 Correct 155 ms 294320 KB Output is correct
23 Correct 160 ms 295064 KB Output is correct
24 Correct 164 ms 295564 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 360128 KB Output is correct
2 Correct 1439 ms 423532 KB Output is correct
3 Correct 2025 ms 488932 KB Output is correct
4 Runtime error 2035 ms 524292 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 293160 KB Output is correct
2 Correct 152 ms 293444 KB Output is correct
3 Correct 150 ms 293244 KB Output is correct
4 Correct 151 ms 293348 KB Output is correct
5 Correct 150 ms 293088 KB Output is correct
6 Correct 149 ms 293104 KB Output is correct
7 Correct 150 ms 293160 KB Output is correct
8 Correct 154 ms 293260 KB Output is correct
9 Correct 165 ms 293100 KB Output is correct
10 Correct 151 ms 293276 KB Output is correct
11 Correct 150 ms 293304 KB Output is correct
12 Correct 148 ms 293284 KB Output is correct
13 Correct 152 ms 293788 KB Output is correct
14 Correct 149 ms 294400 KB Output is correct
15 Correct 156 ms 295116 KB Output is correct
16 Correct 165 ms 295748 KB Output is correct
17 Correct 151 ms 293692 KB Output is correct
18 Correct 153 ms 294304 KB Output is correct
19 Correct 153 ms 295060 KB Output is correct
20 Correct 153 ms 295572 KB Output is correct
21 Correct 163 ms 293780 KB Output is correct
22 Correct 155 ms 294320 KB Output is correct
23 Correct 160 ms 295064 KB Output is correct
24 Correct 164 ms 295564 KB Output is correct
25 Correct 895 ms 360128 KB Output is correct
26 Correct 1439 ms 423532 KB Output is correct
27 Correct 2025 ms 488932 KB Output is correct
28 Runtime error 2035 ms 524292 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -