Submission #1133446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133446		kamrad	Klasika (COCI20_klasika)	C++20	110 / 110	3656 ms	426400 KiB

klasika

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("Ofast,unroll-loops")
//pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, int>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define cl                clear
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define FOR(i, st, nd)    for(int i = st; i <= n; i++)
#define rand(l, r)        uniform_int_distribution<int64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const int Mod    = 1e9 + 7; //998244353;
const int LG     = 30;
const int SQ     = 500;
const int Inf    = 2e9 + 10;
const int maxN   = 2e5 + 10;

int tme;
int cur;
int L[maxN];
int R[maxN];
int xr[maxN];
int idx[maxN];

vector <int> ans;
vector <int> child[maxN];
vector <pi3> query;

bitset <LG> ToChange;
bitset <LG> out;

struct Node {
	Node *c[2];
	set <int> val;

	Node() {
		c[0] = c[1] = nullptr;
	}

	void AddChild(int id) {
		if(c[id] == nullptr)
			c[id] = new Node();
	}

	void Add(int idx, int x) {
		val.insert(x);
		if(idx < 0)
			return;

		int bit = ToChange[idx];
		AddChild(bit);
		c[bit]->Add(idx-1, x);
	}

	void Rem(int idx, int x) {
		val.erase(x);
		if(idx < 0)
			return;

		int bit = ToChange[idx];
		c[bit]->Rem(idx-1, x);
	}

	bool check(int l, int r) {
		auto it = val.lower_bound(l);
		if(it != val.end() and *it <= r)
			return true;
		return false;
	}

	void GetMax(int idx, int l, int r) {
		if(idx < 0)
			return;

		int bit = ToChange[idx];
		if(c[1-bit] != nullptr and c[1-bit]->check(l, r)) {
			out[idx] = 1-bit;
			c[1-bit]->GetMax(idx-1, l, r);
		}
		else if(c[bit] != nullptr) {	
			out[idx] = bit;
			c[bit]->GetMax(idx-1, l, r);
		}
	}
} root;

void dfs(int u) {
	idx[u] = tme;
	L[u] = tme;
	tme++;

	for(auto v : child[u])
		dfs(v);

	R[u] = tme-1;
}

int Convert(bitset <LG> a, bitset <LG> b) {
	int ret = 0;
	for(int i = 0; i < LG; i++) {
		ret += (1<<i)*(a[i] != b[i]);
	}
	return ret;
}

int main() {
	IOS;

	int q;
	cin >> q;

	cur = 2;
	for(int i = 1; i <= q; i++) {
		string t;
		int x, y;
		cin >> t >> x >> y;

		if(t == "Add") {
			child[x].pb(cur);
			xr[cur] = xr[x]^y;
			query.pb({{cur, 0}, 1});
			cur++;
		}
		else {
			query.pb({{x, y}, 2});
		}
	}
	reverse(all(query));

	tme = 1;
	dfs(1);

	for(int i = 1; i < cur; i++) {
		ToChange = xr[i];
		root.Add(LG-1, idx[i]);
	}

	for(auto p : query) {
		int x = p.F.F;
		int y = p.F.S;
		int t = p.S;

		if(t == 1) {
			ToChange = xr[x];
			root.Rem(LG-1, idx[x]);
		}
		else {
			ToChange = xr[x];
			root.GetMax(LG-1, L[y], R[y]);
			ans.pb(Convert(ToChange, out));
		}
	}

	reverse(all(ans));
	for(auto x : ans)
		cout << x << "\n";
}

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