oj.uz

Submission #349126

# Submission time Handle Problem Language Result Execution time Memory
349126 2021-01-16T17:47:16 Z VodkaInTheJar Game (IOI13_game) C++14
100 / 100
 9439 ms 58752 KB 
#include <bits/stdc++.h>
#include "game.h"
 
using namespace std;
mt19937 random_generator(23799931);
 
long long gcd(long long a, long long b)
{
	while (b)
	{
		long long r = a % b;
		a = b;
		b = r; 
	}
	
	return a;
}
 
struct node
{
	long long val, subtree_val;
	int key, prior; 
	node *left, *right;
	
	node() {}
	node(int _key, long long _val) {key = _key, val = subtree_val = _val, prior = random_generator(), left = right = nullptr;}
};

long long subtree_val(node *x)
{
	return x ? x->subtree_val : 0;
}

void recalc(node *&x)
{
	if (!x)
	return;
	
	x->subtree_val = gcd(gcd(subtree_val(x->left), subtree_val(x->right)), x->val);
}

void merge(node *a, node *b, node *&ans)
{
	if (!a || !b)
	ans = a ? a : b; 
	
	else 
	if (a->prior > b->prior)
	merge(a->right, b, a->right), ans = a;
	
	else 
	merge(a, b->left, b->left), ans = b;
	
	recalc(ans);
}

void split(node *x, pair <int, long long> split_val, node *&l, node *&r)
{
	if (!x)
	l = r = nullptr;
	
	else 
	if (make_pair(x->key, x->val) <= split_val)
	{
		split(x->right, split_val, x->right, r);
	
		l = x; 
		recalc(l);
	}
	
	else 
	{
		split(x->left, split_val, l, x->left);
		
		r = x;
		recalc(r);
	}
}

void insert(node *&ans, node *x)
{
	if (!ans)
	ans = x;
	
	else
	if (x->prior > ans->prior)
	{
		split(ans, make_pair(x->key, x->val), x->left, x->right);
		
		ans = x;
		recalc(ans);
	}
	
	else 
	if (make_pair(x->key, x->val) < make_pair(ans->key, ans->val))
	insert(ans->left, x);
	
	else 
	insert(ans->right, x);
	
	recalc(ans);
}

void erase(node *&ans, int key, long long val)
{
	if (!ans)
	return;
	
	if (make_pair(ans->key, ans->val) == make_pair(key, val))
	merge(ans->left, ans->right, ans);
	
	else 
	if (make_pair(key, val) < make_pair(ans->key, ans->val))
	erase(ans->left, key, val);
	
	else 
	erase(ans->right, key, val);
	
	recalc(ans);
}


long long get(node *x, int l, int r)
{
	pair <node*, node*> temp, temp1;
	split(x, make_pair(r+1, -1), temp.first, temp.second);
	split(temp.first, make_pair(l, -1), temp1.first, temp1.second);
	
	long long ans = subtree_val(temp1.second);
	
	merge(temp1.first, temp1.second, temp.first);
	merge(temp.first, temp.second, x);
	
	return ans;
}
 
struct segment_tree
{
	node *root; 
	segment_tree *left, *right;
	
	segment_tree() {root = nullptr, left = right = nullptr;}
};

map <pair <int, int>, long long> mp;
segment_tree *tr;
int r, c; 
void init(int _r, int _c)
{
	tr = new segment_tree();
	r = _r;
	c = _c; 
}

void big_erase(segment_tree *&tr, int l, int r, int x, int y, long long val)
{
	if (!tr)
	return;
	
	erase(tr->root, y, val);
	if (l == r)
	return;
	
	int mid = (l + r) / 2;
	if (x <= mid)
	big_erase(tr->left, l, mid, x, y, val);
	
	else 
	big_erase(tr->right, mid + 1, r, x, y, val);
}

void big_insert(segment_tree *&tr, int l, int r, int x, int y, long long val)
{
	insert(tr->root, new node(y, val));
	if (l == r)
	return;
	
	int mid = (l + r) / 2; 
	if (x <= mid)
	{
		if (!tr->left)
		tr->left = new segment_tree();
		
		big_insert(tr->left, l, mid, x, y, val);
	}
	
	else 
	{
		if (!tr->right)
		tr->right = new segment_tree();
		
		big_insert(tr->right, mid + 1, r, x, y, val);
	}
}

long long big_get(segment_tree *&tr, int l, int r, int lx, int rx, int ly, int ry)
{
	if (!tr || l > rx || r < lx)
	return 0;
	
	if (l >= lx && r <= rx)
	return get(tr->root, ly, ry);
	
	int mid = (l + r) / 2;
	return gcd(big_get(tr->left, l, mid, lx, rx, ly, ry), big_get(tr->right, mid + 1, r, lx, rx, ly, ry));
}

void update(int p, int q, long long k)
{
	if (mp.count({p, q}))
	big_erase(tr, 0, r-1, p, q, mp[{p, q}]);
	
	mp[{p, q}] = k;
	big_insert(tr, 0, r-1, p, q, k);
}
 
long long calculate(int p, int q, int u, int v)
{
	return big_get(tr, 0, r-1, p, u, q, v);
}

/*
int main()
{
	int r1, c1, q;
	cin >> r1 >> c1 >> q;
	
	init(r1, c1);
	while (q--)
	{
		int type;
		cin >> type;
		
		if (type == 1)
		{
			int p, q;
			long long k;
			cin >> p >> q >> k;
			
			update(p, q, k);
		}
		
		else 
		{
			int p, q, u, v;
			cin >> p >> q >> u >> v;
			
			cout << calculate(p, q, u, v) << endl; 
		}
	}
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1133 ms 7184 KB Output is correct
5 Correct 480 ms 7404 KB Output is correct
6 Correct 1342 ms 4236 KB Output is correct
7 Correct 1560 ms 3912 KB Output is correct
8 Correct 1039 ms 3280 KB Output is correct
9 Correct 1477 ms 3984 KB Output is correct
10 Correct 1400 ms 3620 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1771 ms 10288 KB Output is correct
13 Correct 4750 ms 9560 KB Output is correct
14 Correct 773 ms 9124 KB Output is correct
15 Correct 5207 ms 9980 KB Output is correct
16 Correct 492 ms 10092 KB Output is correct
17 Correct 2243 ms 7532 KB Output is correct
18 Correct 4135 ms 10564 KB Output is correct
19 Correct 3379 ms 10648 KB Output is correct
20 Correct 3230 ms 10296 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1168 ms 7180 KB Output is correct
13 Correct 513 ms 7404 KB Output is correct
14 Correct 1371 ms 4332 KB Output is correct
15 Correct 1599 ms 4108 KB Output is correct
16 Correct 1027 ms 3436 KB Output is correct
17 Correct 1509 ms 4212 KB Output is correct
18 Correct 1404 ms 3796 KB Output is correct
19 Correct 1770 ms 10376 KB Output is correct
20 Correct 4791 ms 9500 KB Output is correct
21 Correct 790 ms 9068 KB Output is correct
22 Correct 5152 ms 9980 KB Output is correct
23 Correct 494 ms 10092 KB Output is correct
24 Correct 2229 ms 7532 KB Output is correct
25 Correct 4080 ms 10452 KB Output is correct
26 Correct 3245 ms 10596 KB Output is correct
27 Correct 3161 ms 10168 KB Output is correct
28 Correct 1350 ms 28012 KB Output is correct
29 Correct 2509 ms 28608 KB Output is correct
30 Correct 6759 ms 22896 KB Output is correct
31 Correct 5695 ms 22220 KB Output is correct
32 Correct 1064 ms 19176 KB Output is correct
33 Correct 1588 ms 19184 KB Output is correct
34 Correct 488 ms 25324 KB Output is correct
35 Correct 2532 ms 15860 KB Output is correct
36 Correct 4792 ms 25848 KB Output is correct
37 Correct 3823 ms 26076 KB Output is correct
38 Correct 3882 ms 25400 KB Output is correct
39 Correct 3165 ms 21100 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1110 ms 7096 KB Output is correct
13 Correct 481 ms 7404 KB Output is correct
14 Correct 1310 ms 4204 KB Output is correct
15 Correct 1515 ms 4076 KB Output is correct
16 Correct 1020 ms 3436 KB Output is correct
17 Correct 1450 ms 4192 KB Output is correct
18 Correct 1364 ms 3820 KB Output is correct
19 Correct 1756 ms 10516 KB Output is correct
20 Correct 4686 ms 9580 KB Output is correct
21 Correct 768 ms 9196 KB Output is correct
22 Correct 5090 ms 10208 KB Output is correct
23 Correct 494 ms 10348 KB Output is correct
24 Correct 2226 ms 7404 KB Output is correct
25 Correct 4018 ms 10860 KB Output is correct
26 Correct 3262 ms 10664 KB Output is correct
27 Correct 3153 ms 9964 KB Output is correct
28 Correct 1341 ms 27628 KB Output is correct
29 Correct 2505 ms 28448 KB Output is correct
30 Correct 6756 ms 22620 KB Output is correct
31 Correct 5695 ms 22112 KB Output is correct
32 Correct 1052 ms 18880 KB Output is correct
33 Correct 1601 ms 19176 KB Output is correct
34 Correct 480 ms 25196 KB Output is correct
35 Correct 2529 ms 15596 KB Output is correct
36 Correct 4861 ms 25776 KB Output is correct
37 Correct 3800 ms 25836 KB Output is correct
38 Correct 3838 ms 25136 KB Output is correct
39 Correct 1759 ms 56556 KB Output is correct
40 Correct 4026 ms 58752 KB Output is correct
41 Correct 9439 ms 48332 KB Output is correct
42 Correct 8650 ms 46324 KB Output is correct
43 Correct 811 ms 53232 KB Output is correct
44 Correct 1724 ms 42476 KB Output is correct
45 Correct 3188 ms 27768 KB Output is correct
46 Correct 5986 ms 57408 KB Output is correct
47 Correct 6001 ms 57516 KB Output is correct
48 Correct 5908 ms 57064 KB Output is correct
49 Correct 1 ms 492 KB Output is correct