oj.uz

Submission #437345

# Submission time Handle Problem Language Result Execution time Memory
437345 2021-06-26T07:46:15 Z cmwqfcmwqf Game (IOI13_game) C++14
100 / 100
 7411 ms 28532 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 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, (int)rnd(), y, v, v};
	return cnt;
}

void pushup(int node) { 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 &rt, int x, int y)
{
	if(!rt) return 0;
	int u, v, w;
	split(rt, y, u, v);
	split(u, x - 1, u, w);
	LL ans = w ? tree[w].g : 0;
	rt = merge(merge(u, w), v);
	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 2 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 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 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 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1008 ms 5700 KB Output is correct
5 Correct 476 ms 5956 KB Output is correct
6 Correct 1595 ms 2796 KB Output is correct
7 Correct 1860 ms 2416 KB Output is correct
8 Correct 1136 ms 2480 KB Output is correct
9 Correct 1756 ms 2652 KB Output is correct
10 Correct 1447 ms 2084 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 204 KB Output is correct
2 Correct 2 ms 312 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 2 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 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 1532 ms 6892 KB Output is correct
13 Correct 3691 ms 2428 KB Output is correct
14 Correct 516 ms 904 KB Output is correct
15 Correct 3953 ms 2940 KB Output is correct
16 Correct 517 ms 4036 KB Output is correct
17 Correct 2418 ms 3276 KB Output is correct
18 Correct 3935 ms 4360 KB Output is correct
19 Correct 3493 ms 4600 KB Output is correct
20 Correct 3307 ms 3932 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 256 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 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 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 1150 ms 5612 KB Output is correct
13 Correct 570 ms 5976 KB Output is correct
14 Correct 1636 ms 2724 KB Output is correct
15 Correct 1767 ms 2420 KB Output is correct
16 Correct 1136 ms 2464 KB Output is correct
17 Correct 1699 ms 2616 KB Output is correct
18 Correct 1568 ms 2092 KB Output is correct
19 Correct 1630 ms 6884 KB Output is correct
20 Correct 3639 ms 2432 KB Output is correct
21 Correct 503 ms 836 KB Output is correct
22 Correct 3947 ms 2992 KB Output is correct
23 Correct 512 ms 4096 KB Output is correct
24 Correct 2324 ms 3136 KB Output is correct
25 Correct 3899 ms 4372 KB Output is correct
26 Correct 3537 ms 4700 KB Output is correct
27 Correct 3326 ms 4052 KB Output is correct
28 Correct 1318 ms 12596 KB Output is correct
29 Correct 2316 ms 15652 KB Output is correct
30 Correct 4978 ms 10680 KB Output is correct
31 Correct 4341 ms 8380 KB Output is correct
32 Correct 711 ms 872 KB Output is correct
33 Correct 1039 ms 1096 KB Output is correct
34 Correct 757 ms 12872 KB Output is correct
35 Correct 2539 ms 7516 KB Output is correct
36 Correct 5001 ms 13112 KB Output is correct
37 Correct 4061 ms 13320 KB Output is correct
38 Correct 4019 ms 12776 KB Output is correct
39 Correct 3437 ms 10516 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 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 2 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 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 1061 ms 5660 KB Output is correct
13 Correct 468 ms 6024 KB Output is correct
14 Correct 1524 ms 2804 KB Output is correct
15 Correct 1748 ms 2588 KB Output is correct
16 Correct 1135 ms 2504 KB Output is correct
17 Correct 1699 ms 2584 KB Output is correct
18 Correct 1444 ms 2356 KB Output is correct
19 Correct 1580 ms 6884 KB Output is correct
20 Correct 3566 ms 2288 KB Output is correct
21 Correct 504 ms 836 KB Output is correct
22 Correct 3810 ms 2756 KB Output is correct
23 Correct 524 ms 4036 KB Output is correct
24 Correct 2329 ms 3260 KB Output is correct
25 Correct 3926 ms 4496 KB Output is correct
26 Correct 3604 ms 4584 KB Output is correct
27 Correct 3352 ms 4132 KB Output is correct
28 Correct 1307 ms 12636 KB Output is correct
29 Correct 2464 ms 15884 KB Output is correct
30 Correct 4699 ms 10624 KB Output is correct
31 Correct 4221 ms 8604 KB Output is correct
32 Correct 835 ms 884 KB Output is correct
33 Correct 1085 ms 1056 KB Output is correct
34 Correct 877 ms 12908 KB Output is correct
35 Correct 2696 ms 7584 KB Output is correct
36 Correct 5012 ms 13060 KB Output is correct
37 Correct 3970 ms 13268 KB Output is correct
38 Correct 4156 ms 12672 KB Output is correct
39 Correct 2012 ms 26500 KB Output is correct
40 Correct 4094 ms 28532 KB Output is correct
41 Correct 7196 ms 21940 KB Output is correct
42 Correct 6656 ms 16664 KB Output is correct
43 Correct 1517 ms 26592 KB Output is correct
44 Correct 1201 ms 1028 KB Output is correct
45 Correct 3501 ms 10420 KB Output is correct
46 Correct 7411 ms 26888 KB Output is correct
47 Correct 7344 ms 26772 KB Output is correct
48 Correct 6385 ms 26532 KB Output is correct
49 Correct 1 ms 204 KB Output is correct