Submission #197997

#	Time	Username	Problem	Language	Result	Execution time	Memory
197997		ami	Klasika (COCI20_klasika)	C++17	110 / 110	1332 ms	281708 KiB

klasika

#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
using namespace std;
typedef long long ll;

struct node {
	int next[2];
	node() {
		next[0]=next[1]=-1;
	}
};


const int bitlen=30;
struct trie {
	vector<node> t;
	trie():t(1) {}

	void new_node(int v,int bit) {
		t[v].next[bit]=sz(t);
		t.emplace_back();
	}

	void add(int x) {
		int v=0;
		per(i,0,bitlen+1) {
			int bit=x>>i&1;
			if (t[v].next[bit]==-1) new_node(v,bit);
			v=t[v].next[bit];
		}
	}

	int getmax(int x) const {
		int v=0,res=0;
		per(i,0,bitlen+1) {
			int bit=x>>i&1;
			if (t[v].next[!bit]!=-1) {
				res^=1<<i;
				bit=!bit;
			}
			if (t[v].next[bit]==-1) return 0;
			v=t[v].next[bit];
		}
		return res;
	}
};


struct segtree {
	using Item = trie;
	using Change = int;
	using Result = int;

	int n;
	vector<Item> tr;
	vector<bool> used;

	explicit segtree(int sz):n(sz),tr(2*n),used(2*n) {}

	static void modify(Item &it, const Change &x) {
		it.add(x);
	}

	static void check(Result &res, const Item &it, int x) {
		res=max(res,it.getmax(x));
	}

	void mark_used(int l, int r) {
		l+=n, r+=n;
		while (l<=r) {
			if (l%2==1) used[l]=true;
			if (r%2==0) used[r]=true;
			l=(l+1)/2;
			r=(r-1)/2;
		}
	}

	void add(int i, const Change &x) {
		for (i+=n; i>0; i/=2) if (used[i]) modify(tr[i],x);
	}

	Result query(int l, int r, int x) const {
		Result res{};
		l+=n, r+=n;
		while (l<=r) {
			if (l%2==1) check(res,tr[l],x);
			if (r%2==0) check(res,tr[r],x);
			l=(l+1)/2;
			r=(r-1)/2;
		}
		return res;
	}

	Item& operator[](int i) {
		return tr[i+n];
	}
};

vector<vector<int>> adj(1);
vector<int> xum(1);
vector<pair<int,int>> tio(1);

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	int Q;
	cin>>Q;
	vector<tuple<string,int,int>> qs;
	rep(i,0,Q) {
		string s;
		int a,b;
		cin>>s>>a>>b;
		if (s=="Add") {
			a--;
			int v=sz(adj);
			adj[a].emplace_back(v);
			adj.emplace_back();
			tio.emplace_back();
			xum.emplace_back(xum[a]^b);
			a=v;
		} else {
			a--, b--;
		}
		qs.emplace_back(s,a,b);
	}

	int time=0;
	function<void(int)> dfs=[&](int v) {
		tio[v].first=time++;
		fore(adj[v],u) dfs(u);
		tio[v].second=time-1;
	};
	dfs(0);

	segtree st(sz(xum));
	fore(qs,&q) {
		string s;
		int a,b;
		tie(s,a,b)=q;
		if (s=="Query") st.mark_used(tio[b].first,tio[b].second);
	}

	st.add(0,xum[0]);
	fore(qs,&q) {
		string s;
		int a,b;
		tie(s,a,b)=q;
		if (s=="Add") {
			st.add(tio[a].first,xum[a]);
		} else {
			cout<<st.query(tio[b].first,tio[b].second,xum[a])<<'\n';
		}
	}
}

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