oj.uz

Submission #349056

# Submission time Handle Problem Language Result Execution time Memory
349056 2021-01-16T13:21:59 Z VodkaInTheJar Game (IOI13_game) C++14
63 / 100
 2240 ms 256004 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; 
	node *left, *right;
	
	node() {val = 0, left = right = nullptr;}
};

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 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);
}

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));
}

void small_update(segment_tree *&tr, node *&x, int lx, int rx, int ly, int ry, int pos, long long val)
{
	if (ly == ry)
	{
		if (lx == rx)
		x->val = val;
		
		else 
		{
			x->val = 0; 
			if (tr->left)
			x->val = gcd(x->val, small_get(tr->left->root, 0, c-1, ly, ry));
			
			if (tr->right)
			x->val = gcd(x->val, small_get(tr->right->root, 0, c-1, ly, ry));
		}
		
		return;
	}
	
	int mid = (ly + ry) / 2;
	if (pos <= mid)
	{
		if (!x->left)
		x->left = new node();
		
		small_update(tr, x->left, lx, rx, ly, mid, pos, val);
	}
	
	else 
	{
		if (!x->right)
		x->right = new node();
		
		small_update(tr, x->right, lx, rx, mid + 1, ry, pos, val);
	}
	
	merge(x);
}

void big_update(segment_tree *&tr, int l, int r, int x, int y, long long val)
{
	if (l == r)
	{
		small_update(tr, tr->root, l, r, 0, c-1, y, val);
		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);
	}
	
	small_update(tr, tr->root, l, r, 0, c-1, 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-1, 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); 
}

/*
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 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 492 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 384 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 577 ms 17512 KB Output is correct
5 Correct 459 ms 17260 KB Output is correct
6 Correct 592 ms 14964 KB Output is correct
7 Correct 596 ms 14700 KB Output is correct
8 Correct 391 ms 11136 KB Output is correct
9 Correct 591 ms 14828 KB Output is correct
10 Correct 585 ms 14444 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 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 492 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 372 KB Output is correct
12 Correct 1050 ms 20076 KB Output is correct
13 Correct 1590 ms 10348 KB Output is correct
14 Correct 339 ms 5740 KB Output is correct
15 Correct 1907 ms 13296 KB Output is correct
16 Correct 307 ms 22508 KB Output is correct
17 Correct 948 ms 16712 KB Output is correct
18 Correct 1582 ms 24192 KB Output is correct
19 Correct 1376 ms 24188 KB Output is correct
20 Correct 1258 ms 23660 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 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 492 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 603 ms 17644 KB Output is correct
13 Correct 461 ms 17516 KB Output is correct
14 Correct 553 ms 15080 KB Output is correct
15 Correct 607 ms 14700 KB Output is correct
16 Correct 388 ms 11116 KB Output is correct
17 Correct 593 ms 14884 KB Output is correct
18 Correct 578 ms 14336 KB Output is correct
19 Correct 1006 ms 20076 KB Output is correct
20 Correct 1669 ms 10476 KB Output is correct
21 Correct 350 ms 5884 KB Output is correct
22 Correct 1917 ms 13420 KB Output is correct
23 Correct 307 ms 22508 KB Output is correct
24 Correct 861 ms 16492 KB Output is correct
25 Correct 1582 ms 23952 KB Output is correct
26 Correct 1306 ms 24300 KB Output is correct
27 Correct 1257 ms 23532 KB Output is correct
28 Correct 1280 ms 256000 KB Output is correct
29 Runtime error 2227 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 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 492 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 591 ms 17516 KB Output is correct
13 Correct 457 ms 17388 KB Output is correct
14 Correct 537 ms 15196 KB Output is correct
15 Correct 604 ms 14700 KB Output is correct
16 Correct 387 ms 11244 KB Output is correct
17 Correct 576 ms 15212 KB Output is correct
18 Correct 538 ms 14444 KB Output is correct
19 Correct 1004 ms 20196 KB Output is correct
20 Correct 1594 ms 10292 KB Output is correct
21 Correct 345 ms 5996 KB Output is correct
22 Correct 1902 ms 13292 KB Output is correct
23 Correct 305 ms 22508 KB Output is correct
24 Correct 852 ms 16492 KB Output is correct
25 Correct 1520 ms 23972 KB Output is correct
26 Correct 1290 ms 24044 KB Output is correct
27 Correct 1237 ms 23788 KB Output is correct
28 Correct 1256 ms 256000 KB Output is correct
29 Runtime error 2240 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -