Submission #348676

#	Time	Username	Problem	Language	Result	Execution time	Memory
348676		VodkaInTheJar	Game (IOI13_game)	C++14	0 / 100	1 ms	364 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

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; 
	node *left, *right;
	
	node() {val = 0, left = right = nullptr;}
};

void merge(node *&x)
{
	x->val = 0;
	if (x->left)
	x->val = gcd(x->val, x->left->val);
	
	if (x->right)
	x->val = gcd(x->val, x->right->val);
}

void small_update(node *&x, int l, int r, int pos, long long val)
{
	if (l == r)
	{
		x->val = val;
		return;
	}
	
	int mid = (l + r) / 2;
	if (pos <= mid)
	{
		if (!x->left)
		x->left = new node();
		
		small_update(x->left, l, mid, pos, val);
	}
	
	else 
	{
		if (!x->right)
		x->right = new node();
		
		small_update(x->right, mid + 1, r, pos, val);
	}
	
	merge(x);
}

long long small_get(node *x, int l, int r, int ll, int rr)
{
	if (!x || l > rr || r < ll)
	return 0;
	
	if (l >= ll && r <= rr)
	return x->val;
	
	int mid = (l + r) / 2;
	return gcd(small_get(x->left, l, mid, ll, rr), small_get(x->right, mid + 1, r, ll, rr));
}

struct segment_tree
{
	node *root; 
	segment_tree *left, *right;
	
	segment_tree() {root = new node(), 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_update(segment_tree *&tr, int l, int r, int x, int y, long long val)
{
	small_update(tr->root, 0, c, y, val);
	
	if (l == r)
	return;
	
	int mid = (l + r) / 2;
	if (x <= mid)
	{
		if (!tr->left)
		tr->left = new segment_tree();
		
		big_update(tr->left, l, mid, x, y, val);
	}
	
	else 
	{
		if (!tr->right)
		tr->right = new segment_tree();
		
		big_update(tr->right, mid + 1, r, x, y, val);
	}
}

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

void update(int p, int q, long long k)
{
	big_update(tr, 0, r, p, q, k);
}

long long calculate(int p, int q, int u, int v)
{
	return big_get(tr, 0, r, p, u, q, v); 
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20