oj.uz

Submission #349060

# Submission time Handle Problem Language Result Execution time Memory
349060 2021-01-16T13:53:28 Z VodkaInTheJar Game (IOI13_game) C++14
0 / 100
 1 ms 364 KB 
#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; 
	int left, right; 
	
	node() {val = 0, left = right = -1;}
};

struct segment_tree
{
	vector <node> tr;
	int left, right; 
	
	segment_tree() {tr.push_back(node()), left = right = -1;}
};

vector <segment_tree> tr; 

int r, c; 
void init(int _r, int _c)
{
	tr.push_back(segment_tree());
	r = _r;
	c = _c; 
}

void merge(int idxx, int idxy)
{
	tr[idxx].tr[idxy].val = 0;
	
	if (tr[idxx].tr[idxy].left != -1)
	tr[idxx].tr[idxy].val = gcd(tr[idxx].tr[idxy].val, tr[idxx].tr[tr[idxx].tr[idxy].left].val);
	
	if (tr[idxx].tr[idxy].right != -1)
	tr[idxx].tr[idxy].val = gcd(tr[idxx].tr[idxy].val, tr[idxx].tr[tr[idxx].tr[idxy].right].val);
}

int mid; 
long long small_get(int idxx, int idxy, int l, int r, int ll, int rr)
{
	if (idxy == -1 || l > rr || r < ll)
	return 0;
	
	if (l >= ll && r <= rr)
	return tr[idxx].tr[idxy].val;
	
	mid = (l + r) / 2;
	return gcd(small_get(idxx, tr[idxx].tr[idxy].left, l, mid, ll, rr), small_get(idxx, tr[idxx].tr[idxy].right, mid + 1, r, ll, rr));
}

void small_update(int idxx, int idxy, int lx, int rx, int ly, int ry, int pos, long long val)
{
	if (ly == ry)
	{
		if (lx == rx)
		tr[idxx].tr[idxy].val = val;
		
		else 
		{
			tr[idxx].tr[idxy].val = 0; 
			if (tr[idxx].left != -1)
			tr[idxx].tr[idxy].val = gcd(tr[idxx].tr[idxy].val, small_get(tr[idxx].left, 0, 0, c-1, ly, ry));
			
			if (tr[idxx].right != -1)
			tr[idxx].tr[idxy].val = gcd(tr[idxx].tr[idxy].val, small_get(tr[idxx].right, 0, 0, c-1, ly, ry));
		}
		
		return;
	}
	
	mid = (ly + ry) / 2;
	if (pos <= mid)
	{
		if (tr[idxx].tr[idxy].left == -1)
		{
			tr[idxx].tr.push_back(node());
			tr[idxx].tr[idxy].left = (int)tr[idxx].tr.size() - 1;
		}
		
		small_update(idxx, tr[idxx].tr[idxy].left, lx, rx, ly, mid, pos, val);
	}
	
	else 
	{
		if (tr[idxx].tr[idxy].right == -1)
		{
			tr[idxx].tr.push_back(node());
			tr[idxx].tr[idxy].right = (int)tr[idxx].tr.size() - 1; 
		}
		
		small_update(idxx, tr[idxx].tr[idxy].right, lx, rx, mid + 1, ry, pos, val);
	}
	
	merge(idxx, idxy);
}

void big_update(int idxx, int l, int r, int x, int y, long long val)
{
	if (l == r)
	{
		small_update(idxx, 0, l, r, 0, c-1, y, val);
		return;
	}
	
	mid = (l + r) / 2;
	if (x <= mid)
	{
		if (tr[idxx].left == -1)
		{
			tr.push_back(segment_tree());
			tr[idxx].left = (int)tr.size() - 1;
		}
		
		big_update(tr[idxx].left, l, mid, x, y, val);
	}
	
	else 
	{
		if (tr[idxx].right == -1)
		{
			tr.push_back(segment_tree());
			tr[idxx].right = (int)tr.size() - 1; 
		}
		
		big_update(tr[idxx].right, mid + 1, r, x, y, val);
	}
	
	small_update(idxx, 0, l, r, 0, c-1, y, val);
}

long long big_get(int idxx, int l, int r, int lx, int rx, int ly, int ry)
{
	if (idxx == -1 || l > rx || r < lx)
	return 0;
	
	if (l >= lx && r <= rx)
	return small_get(idxx, 0, 0, c-1, ly, ry);
	
	mid = (l + r) / 2; 
	return gcd(big_get(tr[idxx].left, l, mid, lx, rx, ly, ry), big_get(tr[idxx].right, mid + 1, r, lx, rx, ly, ry));
}

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

long long calculate(int p, int q, int u, int v)
{
	return big_get(0, 0, r, 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

# Verdict Execution time Memory 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

# 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 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory 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 #4
0 / 17.0

# Verdict Execution time Memory 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 #5
0 / 20.0

# Verdict Execution time Memory 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 -