Submission #349125

#	Time	Username	Problem	Language	Result	Execution time	Memory
349125		VodkaInTheJar	Game (IOI13_game)	C++14	37 / 100	13085 ms	7404 KiB

game

#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 == 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)
{
	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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20