oj.uz

Submission #437336

# Submission time Handle Problem Language Result Execution time Memory
437336 2021-06-26T07:42:12 Z cmwqfcmwqf Game (IOI13_game) C++14
80 / 100
 5238 ms 51268 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 * 30 + 1];

struct Seg
{
	int l, r;
	int rt;
}T[maxN * 30 + 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 204 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 2 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 1205 ms 5688 KB Output is correct
5 Correct 482 ms 6024 KB Output is correct
6 Correct 1559 ms 2704 KB Output is correct
7 Correct 1735 ms 2344 KB Output is correct
8 Correct 1280 ms 2512 KB Output is correct
9 Correct 1780 ms 2612 KB Output is correct
10 Correct 1547 ms 2116 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 3 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 2 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 2105 ms 6704 KB Output is correct
13 Correct 3801 ms 2352 KB Output is correct
14 Correct 616 ms 784 KB Output is correct
15 Correct 4179 ms 2756 KB Output is correct
16 Correct 603 ms 4012 KB Output is correct
17 Correct 2475 ms 3168 KB Output is correct
18 Correct 3881 ms 4292 KB Output is correct
19 Correct 3576 ms 4516 KB Output is correct
20 Correct 3467 ms 3940 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 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 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 268 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1184 ms 5616 KB Output is correct
13 Correct 501 ms 5928 KB Output is correct
14 Correct 1584 ms 2608 KB Output is correct
15 Correct 1917 ms 2388 KB Output is correct
16 Correct 1128 ms 2616 KB Output is correct
17 Correct 1654 ms 2504 KB Output is correct
18 Correct 1408 ms 2116 KB Output is correct
19 Correct 1537 ms 6816 KB Output is correct
20 Correct 3625 ms 2336 KB Output is correct
21 Correct 505 ms 836 KB Output is correct
22 Correct 3829 ms 2816 KB Output is correct
23 Correct 518 ms 4136 KB Output is correct
24 Correct 2335 ms 3196 KB Output is correct
25 Correct 4046 ms 4496 KB Output is correct
26 Correct 3469 ms 4548 KB Output is correct
27 Correct 3356 ms 3828 KB Output is correct
28 Correct 1427 ms 12532 KB Output is correct
29 Correct 2581 ms 15656 KB Output is correct
30 Correct 5134 ms 10568 KB Output is correct
31 Correct 4433 ms 8560 KB Output is correct
32 Correct 719 ms 824 KB Output is correct
33 Correct 1055 ms 1080 KB Output is correct
34 Correct 827 ms 12868 KB Output is correct
35 Correct 2698 ms 7488 KB Output is correct
36 Correct 5010 ms 13008 KB Output is correct
37 Correct 4355 ms 13256 KB Output is correct
38 Correct 4331 ms 12588 KB Output is correct
39 Correct 3886 ms 10496 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
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 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1113 ms 5784 KB Output is correct
13 Correct 495 ms 6104 KB Output is correct
14 Correct 1529 ms 2632 KB Output is correct
15 Correct 1744 ms 2408 KB Output is correct
16 Correct 1131 ms 2548 KB Output is correct
17 Correct 1680 ms 2500 KB Output is correct
18 Correct 1490 ms 2132 KB Output is correct
19 Correct 1538 ms 6796 KB Output is correct
20 Correct 3608 ms 2508 KB Output is correct
21 Correct 534 ms 968 KB Output is correct
22 Correct 3800 ms 2772 KB Output is correct
23 Correct 516 ms 4016 KB Output is correct
24 Correct 2303 ms 3356 KB Output is correct
25 Correct 3909 ms 4532 KB Output is correct
26 Correct 3367 ms 4540 KB Output is correct
27 Correct 3283 ms 4068 KB Output is correct
28 Correct 1341 ms 12564 KB Output is correct
29 Correct 2383 ms 15684 KB Output is correct
30 Correct 4653 ms 10624 KB Output is correct
31 Correct 4238 ms 8408 KB Output is correct
32 Correct 729 ms 896 KB Output is correct
33 Correct 1066 ms 992 KB Output is correct
34 Correct 891 ms 12808 KB Output is correct
35 Correct 2713 ms 7464 KB Output is correct
36 Correct 5238 ms 13076 KB Output is correct
37 Correct 3888 ms 13260 KB Output is correct
38 Correct 3932 ms 12676 KB Output is correct
39 Runtime error 1888 ms 51268 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -