oj.uz

Submission #437366

# Submission time Handle Problem Language Result Execution time Memory
437366 2021-06-26T08:29:56 Z cmwqfcmwqf Game (IOI13_game) C++14
100 / 100
 3698 ms 34036 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
 
mt19937 rnd( time(NULL) );
 
#define LL long long
#define ls tree[node].l
#define rs tree[node].r
 
const int maxN = 2.2e4 + 10;
 
struct Treap
{
	int l, r;
	int ly, ry, key, v;
	LL val, g;
}tree[maxN * 35 + 1];
 
struct Seg
{
	int l, r;
	int rt;
}T[maxN * 35 + 1];
 
int rt, cnt, ct, R, C;
 
LL gcd2(LL X, LL Y)
{
	LL tmp;
	while(X != Y && Y != 0)
	{
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}
 
int new_Node(int y, LL v)
{
	tree[++ cnt] = (Treap){0, 0, y, y, (int)rnd(), y, v, v};
	return cnt;
}
 
void pushup(int node) 
{ 
	tree[node].ly = ls ? tree[ls].ly : tree[node].v;
	tree[node].ry = rs ? tree[rs].ry : tree[node].v;
	tree[node].g = gcd2(tree[ls].g, gcd2(tree[node].val, tree[rs].g)); 
}
 
void split(int node, int k, int &u, int &v)
{
	if(!node) { u = v = 0; return; }
	if(tree[node].v <= k) u = node, split(rs, k, tree[u].r, v);
	else v = node, split(ls, k, u, tree[v].l);
	pushup(node);
}
 
int merge(int u, int v)
{
	if(!u || !v) return u | v;
	if(tree[u].key < tree[v].key)
	{
		tree[u].r = merge(tree[u].r, v);
		return pushup(u), u;
	}
	else
	{
		tree[v].l = merge(u, tree[v].l);
		return pushup(v), v;
	}
}
 
void modify(int &rt, int k, LL val)
{
	int u, v, w;
	split(rt, k, u, v);
	split(u, k - 1, u, w);
	if(!w) w = new_Node(k, val);
	else tree[w].val = tree[w].g = val;
	rt = merge(merge(u, w), v);
}
 
LL ask(int node, int x, int y)
{
	if(!node || tree[node].ly > y || tree[node].ry < x) return 0;
	if(x <= tree[node].ly && tree[node].ry <= y) return tree[node].g;
	LL ans = 0;
	if(x <= tree[node].v && tree[node].v <= y) ans = tree[node].val;
	ans = gcd2(ans, gcd2(ask(ls, x, y), ask(rs, x, y)));
	return ans;
}
 
void change(int &node, int l, int r, int x, int y, LL v)
{
	if(!node) node = ++ ct;
	if(l == r) { modify(T[node].rt, y, v); return; }
	int mid = (l + r) >> 1;
	if(x <= mid) change(T[node].l, l, mid, x, y, v);
	else change(T[node].r, mid + 1, r, x, y, v);
	modify(T[node].rt, y, gcd2(ask(T[ T[node].l ].rt, y, y), ask(T[ T[node].r ].rt, y, y)));
}
 
LL query(int node, int l, int r, int x, int y, int xb, int yb)
{
	if(!node) return 0;
	if(x <= l && r <= y) return ask(T[node].rt, xb, yb);
	int mid = (l + r) >> 1; LL ans = 0;
	if(x <= mid) ans = gcd2(ans, query(T[node].l, l, mid, x, y, xb, yb));
	if(y > mid) ans = gcd2(ans, query(T[node].r, mid + 1, r, x, y, xb, yb));
	return ans;
}
 
void update(int x, int y, LL v)
{
	change(rt, 0, R - 1, x, y, v);
}
 
LL calculate(int xa, int ya, int xb, int yb)
{
	return query(rt, 0, R - 1, xa, xb, ya, yb);
}
 
void init(int r, int c)
{
	R = r; C = c;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 799 ms 6572 KB Output is correct
5 Correct 311 ms 6932 KB Output is correct
6 Correct 680 ms 3728 KB Output is correct
7 Correct 747 ms 3344 KB Output is correct
8 Correct 450 ms 3348 KB Output is correct
9 Correct 759 ms 3452 KB Output is correct
10 Correct 680 ms 3132 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1054 ms 8028 KB Output is correct
13 Correct 1632 ms 3364 KB Output is correct
14 Correct 301 ms 1476 KB Output is correct
15 Correct 1799 ms 3780 KB Output is correct
16 Correct 329 ms 5420 KB Output is correct
17 Correct 905 ms 4216 KB Output is correct
18 Correct 1555 ms 5720 KB Output is correct
19 Correct 1319 ms 5888 KB Output is correct
20 Correct 1226 ms 5284 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 721 ms 6920 KB Output is correct
13 Correct 342 ms 6968 KB Output is correct
14 Correct 663 ms 3856 KB Output is correct
15 Correct 747 ms 3332 KB Output is correct
16 Correct 438 ms 3396 KB Output is correct
17 Correct 710 ms 3452 KB Output is correct
18 Correct 694 ms 3152 KB Output is correct
19 Correct 980 ms 7960 KB Output is correct
20 Correct 1680 ms 3316 KB Output is correct
21 Correct 315 ms 1476 KB Output is correct
22 Correct 1779 ms 3880 KB Output is correct
23 Correct 327 ms 5452 KB Output is correct
24 Correct 905 ms 4188 KB Output is correct
25 Correct 1494 ms 5916 KB Output is correct
26 Correct 1469 ms 5928 KB Output is correct
27 Correct 1236 ms 5340 KB Output is correct
28 Correct 505 ms 15576 KB Output is correct
29 Correct 1635 ms 18676 KB Output is correct
30 Correct 2239 ms 13484 KB Output is correct
31 Correct 1970 ms 10628 KB Output is correct
32 Correct 516 ms 1432 KB Output is correct
33 Correct 671 ms 1692 KB Output is correct
34 Correct 433 ms 15772 KB Output is correct
35 Correct 1169 ms 9088 KB Output is correct
36 Correct 2755 ms 15960 KB Output is correct
37 Correct 1970 ms 16196 KB Output is correct
38 Correct 1955 ms 15592 KB Output is correct
39 Correct 1429 ms 12412 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 750 ms 6152 KB Output is correct
13 Correct 316 ms 6468 KB Output is correct
14 Correct 712 ms 3244 KB Output is correct
15 Correct 734 ms 3016 KB Output is correct
16 Correct 445 ms 2884 KB Output is correct
17 Correct 709 ms 3208 KB Output is correct
18 Correct 668 ms 2716 KB Output is correct
19 Correct 979 ms 7568 KB Output is correct
20 Correct 1632 ms 3024 KB Output is correct
21 Correct 288 ms 964 KB Output is correct
22 Correct 1826 ms 3492 KB Output is correct
23 Correct 321 ms 4932 KB Output is correct
24 Correct 854 ms 3756 KB Output is correct
25 Correct 1431 ms 5336 KB Output is correct
26 Correct 1256 ms 5556 KB Output is correct
27 Correct 1200 ms 5012 KB Output is correct
28 Correct 486 ms 15188 KB Output is correct
29 Correct 1545 ms 18220 KB Output is correct
30 Correct 2133 ms 13040 KB Output is correct
31 Correct 1917 ms 10572 KB Output is correct
32 Correct 497 ms 1056 KB Output is correct
33 Correct 588 ms 1236 KB Output is correct
34 Correct 442 ms 15592 KB Output is correct
35 Correct 1062 ms 8780 KB Output is correct
36 Correct 2373 ms 15760 KB Output is correct
37 Correct 1802 ms 15916 KB Output is correct
38 Correct 1843 ms 15456 KB Output is correct
39 Correct 811 ms 32000 KB Output is correct
40 Correct 2851 ms 34036 KB Output is correct
41 Correct 3219 ms 26700 KB Output is correct
42 Correct 3005 ms 20432 KB Output is correct
43 Correct 930 ms 32108 KB Output is correct
44 Correct 777 ms 1216 KB Output is correct
45 Correct 1469 ms 12616 KB Output is correct
46 Correct 3698 ms 32328 KB Output is correct
47 Correct 3523 ms 32564 KB Output is correct
48 Correct 3373 ms 31852 KB Output is correct
49 Correct 1 ms 204 KB Output is correct