oj.uz

답안 #349101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349101 2021-01-16T16:50:47 Z VodkaInTheJar 게임 (IOI13_game) C++14
0 / 100
 1 ms 512 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);
	
	
	/*
	pair <node*, node*> temp;
	split(ans, x->key, temp.first, temp.second);
	merge(temp.first, x, temp.first); 
	merge(temp.first, temp.second, 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);
	
	/*
	pair <node*, node*> temp, temp1;
	split(ans, x, temp.first, temp.second);
	split(temp.first, x-1, temp1.first, temp1.second);
	merge(temp1.first, temp.second, 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 >= 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)
{
	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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -