oj.uz

Submission #349122

# Submission time Handle Problem Language Result Execution time Memory
349122 2021-01-16T17:39:58 Z VodkaInTheJar Game (IOI13_game) C++14
37 / 100
 13000 ms 9452 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, int val, node *&l, node *&r)
{
	if (!x)
	l = r = nullptr;
	
	else 
	if (x->key <= val)
	{
		split(x->right, val, x->right, r);
	
		l = x; 
		recalc(l);
	}
	
	else 
	{
		split(x->left, 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, x->key, x->left, x->right);
		
		ans = x;
		recalc(ans);
	}
	
	else 
	if (x->key < ans->key)
	insert(ans->left, x);
	
	else 
	insert(ans->right, x);
	
	recalc(ans);
}

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

long long dfs(node *x, int l, int r)
{
	if (!x)
	return 0; 
	
	long long ans = gcd(dfs(x->left, l, r), dfs(x->right, l, r));
	if (x->key >= l && x->key <= r)
	ans = gcd(ans, x->val);
	
	return ans;
}

long long get(node *x, int l, int r)
{
	pair <node*, node*> temp, temp1;
	split(x, r, temp.first, temp.second);
	split(temp.first, 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;}
};

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)
{
	if (!tr)
	return;
	
	erase(tr->root, y);
	if (l == r)
	return;
	
	int mid = (l + r) / 2;
	if (x <= mid)
	big_erase(tr->left, l, mid, x, y);
	
	else 
	big_erase(tr->right, mid + 1, r, x, y);
}

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 == r)
	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)
{
	big_erase(tr, 0, r-1, p, q);
	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 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 384 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 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1592 ms 6764 KB Output is correct
5 Correct 613 ms 9452 KB Output is correct
6 Correct 1952 ms 5992 KB Output is correct
7 Correct 2269 ms 6124 KB Output is correct
8 Correct 1500 ms 5592 KB Output is correct
9 Correct 2174 ms 5888 KB Output is correct
10 Correct 2061 ms 5524 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
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 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 Execution timed out 13015 ms 6192 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
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 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 268 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 1586 ms 6636 KB Output is correct
13 Correct 625 ms 9452 KB Output is correct
14 Correct 1978 ms 6252 KB Output is correct
15 Correct 2273 ms 6124 KB Output is correct
16 Correct 1521 ms 5708 KB Output is correct
17 Correct 2188 ms 6120 KB Output is correct
18 Correct 2080 ms 5588 KB Output is correct
19 Execution timed out 13009 ms 8616 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
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 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 1593 ms 6636 KB Output is correct
13 Correct 605 ms 9452 KB Output is correct
14 Correct 1949 ms 6124 KB Output is correct
15 Correct 2280 ms 5784 KB Output is correct
16 Correct 1515 ms 5528 KB Output is correct
17 Correct 2176 ms 5944 KB Output is correct
18 Correct 2077 ms 5448 KB Output is correct
19 Execution timed out 13056 ms 8288 KB Time limit exceeded
20 Halted 0 ms 0 KB -