Submission #223351

#	Time	Username	Problem	Language	Result	Execution time	Memory
223351		oolimry	Klasika (COCI20_klasika)	C++14	33 / 110	5075 ms	424360 KiB

klasika

#include <bits/stdc++.h>
 
using namespace std;
 
int n = 1;
int cnt = 0;
static vector<int> adj[200005];
static int low[200005];
static int high[200005];
static int XOR[200005];
 
void dfs(int u){
	low[u] = cnt;
	high[u] = cnt;
	cnt++;
	for(int v : adj[u]){
		dfs(v);
		high[u] = max(high[u], high[v]);
	}
}
 
typedef pair<int,int> ii;
vector<ii> queries;

struct seg{
	vector<int> dis;
	vector<bool> tree;
	
	int N;
	
	void get(int l){
		dis.push_back(l);
	}
	
	void getReady(){
		N = dis.size();
		tree.assign(2*N,0);
		//cout << tree.size() << endl;
		sort(dis.begin(),dis.end());
	}
	
	void update(int i){
		i = lower_bound(dis.begin(),dis.end(), i) - dis.begin();
		for(i += N;i > 0;i >>= 1) tree[i] = 1;
	}
	
	int query(int l, int r){
		int res = 0;
		l = lower_bound(dis.begin(),dis.end(), l) - dis.begin();
		r = upper_bound(dis.begin(),dis.end(), r) - dis.begin();
		for(l += N, r += N;l < r;l >>= 1, r >>= 1){
			if(l&1) res |= tree[l++];
			if(r&1) res |= tree[--r];
		}
		return res;
	}
};

static unordered_map<int, seg> m[33];



int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int Q; cin >> Q;
	queries.push_back(ii(-1,0));
	
	while(Q--){
		string s; int a, b; 
		cin >> s >> a >> b;
		if(s[0] == 'A' || s[0] == 'a'){
			a--;
			assert(a < n);
			adj[a].push_back(n);
			XOR[n] = XOR[a] ^ b;
			queries.push_back(ii(-1,n));
			n++;
		}
		else{
			assert(a-1 < n);
			assert(b-1 < n);
			queries.push_back(ii(a-1,b-1));
		}
	}
	
	
	dfs(0);
	
	for(ii q : queries){
		//cout << q.first << " " << q.second << "\n";
		
		if(q.first == -1){
			int pos = low[q.second];
			int x = XOR[q.second];
			
			for(int b = 0;b <= 30;b++){
				m[b][x].get(pos);
				x ^= ((x & (1<<b)));
			}
			
			continue;
		}
	}
	
	unordered_map<int,seg> k;
	for(int b = 0;b <= 30;b++){
		for(auto &x : m[b]){
			(x.second).getReady();
		}
	}
		
	for(ii q : queries){
		//cout << q.first << " " << q.second << "\n";
		
		if(q.first == -1){
			int pos = low[q.second];
			int x = XOR[q.second];
			
			for(int b = 0;b <= 30;b++){
				m[b][x].update(pos);
				x ^= ((x & (1<<b)));
			}
			
			continue;
		}
		
		int other = XOR[q.first];
		int L = low[q.second], R = high[q.second];
		int cur = 0;
		for(int b = 30;b >= 0;b--){
			if((other & (1<<b)) == 0) cur ^= (1 << b);
			
			if(m[b][cur].query(L,R) == 0) cur ^= (1 << b);
		}
		
		cout << (cur ^ other) << "\n";
		
	}
}

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44