Submission #933871

#	Time	Username	Problem	Language	Result	Execution time	Memory
933871		pan	Klasika (COCI20_klasika)	C++17	33 / 110	1728 ms	524288 KiB

klasika

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
struct query
{
	ll a, b, c;
};
struct node
{
	ll layer;
	set<ll> s;
	node *zero, *one;
	node(ll i)
	{
		layer = i;
		zero = one = nullptr;
	}
	void create()
	{
		if (layer>=30 || zero!=nullptr)  return;
		zero = new node(layer +1);
		one = new node(layer +1);
	}
	void insert(ll val, ll time)
	{
		s.insert(time);
		if (layer==30) return; // finish
		create();
		bool bit= val&(1<<(30-layer-1));
		if (bit) one->insert(val, time);
		else zero->insert(val, time);

	}
	ll xorquery(ll val, ll l, ll r)
	{
		if (layer==30) return 0;
		create();
		bool wanted = !(val&((1<<(30-layer-1))));
		if (wanted)
		{
			auto it = one->s.lb(l);
			if (it!=one->s.end() && *it<=r) return one->xorquery(val, l, r)^(1<<(30-layer-1));
			return zero->xorquery(val, l, r);
		}
		else
		{
			auto it = zero->s.lb(l);
			if (it!=zero->s.end() && *it<=r) return zero->xorquery(val, l, r)^(1<<(30-layer-1));
			return one->xorquery(val, l, r);
		}
	}
	
}*root;
ll label = -1;
ll in[200005], out[200005], root_xor[200005];
vector<pi> add[200005];
vector<query> queries;
void dfs(ll x)
{
	in[x] = ++label;
	for (pi u: add[x])
	{
		root_xor[u.f] = root_xor[x]^u.s;
		dfs(u.f);
	}
	out[x] = label;
}
int main()
{
	ll label = 1;
	ll q;
	string s;
	input(q);
	queries.resize(q);
	for (ll i=0; i<q; ++i)
	{
		cin >> s;
		if (s=="Add") queries[i].a = 0;
		else queries[i].a = 1;
		input2(queries[i].b, queries[i].c);
		if (s=="Add") 
		{
			add[queries[i].b].pb(mp(++label, queries[i].c));
		}
		
	}
	dfs(1);
	root = new node(0);
	root->insert(0, 0);
	label  = 1;
	for (ll i=0; i<q; ++i)
	{
		ll a = queries[i].a, b = queries[i].b, c = queries[i].c;
		if (a)
		{
			print(root->xorquery(root_xor[b], in[c], out[c]), '\n');
		}
		else
		{
			++label;
			root->insert(root_xor[label], in[label]);
		}
	}
	return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:11:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
klasika.cpp:99:2: note: in expansion of macro 'input'
   99 |  input(q);
      |  ^~~~~
klasika.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
klasika.cpp:106:3: note: in expansion of macro 'input2'
  106 |   input2(queries[i].b, queries[i].c);
      |   ^~~~~~

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