oj.uz

Submission #933871

# Submission time Handle Problem Language Result Execution time Memory
933871 2024-02-26T12:46:03 Z pan Klasika (COCI20_klasika) C++17
33 / 110
 1728 ms 524288 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 9068 KB Output is correct
3 Correct 3 ms 9352 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9308 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 3 ms 9308 KB Output is correct
12 Correct 3 ms 9560 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 3 ms 9068 KB Output is correct
3 Correct 3 ms 9352 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9308 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 3 ms 9308 KB Output is correct
12 Correct 3 ms 9560 KB Output is correct
13 Correct 5 ms 10844 KB Output is correct
14 Correct 7 ms 12632 KB Output is correct
15 Correct 8 ms 14452 KB Output is correct
16 Correct 10 ms 16216 KB Output is correct
17 Correct 7 ms 10844 KB Output is correct
18 Correct 7 ms 12636 KB Output is correct
19 Correct 8 ms 14376 KB Output is correct
20 Correct 12 ms 15960 KB Output is correct
21 Correct 5 ms 10840 KB Output is correct
22 Correct 9 ms 12460 KB Output is correct
23 Correct 8 ms 14428 KB Output is correct
24 Correct 10 ms 15964 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 171540 KB Output is correct
2 Correct 1084 ms 313708 KB Output is correct
3 Correct 1573 ms 448896 KB Output is correct
4 Runtime error 1728 ms 524288 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 2 ms 9048 KB Output is correct
2 Correct 3 ms 9068 KB Output is correct
3 Correct 3 ms 9352 KB Output is correct
4 Correct 3 ms 9564 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9308 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 3 ms 9308 KB Output is correct
12 Correct 3 ms 9560 KB Output is correct
13 Correct 5 ms 10844 KB Output is correct
14 Correct 7 ms 12632 KB Output is correct
15 Correct 8 ms 14452 KB Output is correct
16 Correct 10 ms 16216 KB Output is correct
17 Correct 7 ms 10844 KB Output is correct
18 Correct 7 ms 12636 KB Output is correct
19 Correct 8 ms 14376 KB Output is correct
20 Correct 12 ms 15960 KB Output is correct
21 Correct 5 ms 10840 KB Output is correct
22 Correct 9 ms 12460 KB Output is correct
23 Correct 8 ms 14428 KB Output is correct
24 Correct 10 ms 15964 KB Output is correct
25 Correct 650 ms 171540 KB Output is correct
26 Correct 1084 ms 313708 KB Output is correct
27 Correct 1573 ms 448896 KB Output is correct
28 Runtime error 1728 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -