oj.uz

Submission #437322

# Submission time Handle Problem Language Result Execution time Memory
437322 2021-06-26T07:18:57 Z denverjin Game (IOI13_game) C++14
100 / 100
 3996 ms 56884 KB 
#include "game.h"
#include <bits/stdc++.h>

typedef long long i64;

i64 gcd(i64 X, i64 Y) {
	i64 tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

struct Node {
	int x, lx, rx;
	i64 v, s;
	int sz;
	int ls, rs;
} t[22000 * 35];

const int null = 0;
int ndsz;

int new_node(int x, i64 v) {
	int i = ++ ndsz;
	t[i].x = t[i].lx = t[i].rx = x;
	t[i].v = t[i].s = v;
	t[i].sz = 1;
	t[i].ls = t[i].rs = null;
	return i;
}

void pushup(int x) {
	t[x].sz = t[t[x].ls].sz + 1 + t[t[x].rs].sz;
	t[x].s = gcd(t[t[x].ls].s, gcd(t[x].v, t[t[x].rs].s));
	t[x].lx = t[x].ls ? t[t[x].ls].lx : t[x].x;
	t[x].rx = t[x].rs ? t[t[x].rs].rx : t[x].x;
}

void split(int x, i64 v, int &a, int &b) {
	if (!x) return void(a = b = null);
	if (t[x].x <= v) a = x, split(t[x].rs, v, t[a].rs, b), pushup(a);
	else b = x, split(t[x].ls, v, a, t[b].ls), pushup(b);
}

std::mt19937 rng;

int rand(int l, int r) { return rng() % (r - l + 1) + l; }

int merge(int a, int b) {
	if (!a || !b) return a | b;
	if (rand(1, t[a].sz + t[b].sz) <= t[a].sz) return t[a].rs = merge(t[a].rs, b), pushup(a), a;
	else return t[b].ls = merge(a, t[b].ls), pushup(b), b;
}

void change(int &i, int p, i64 v) {
	int a, b, c;
	split(i, p, b, c);
	split(b, p - 1, a, b);
	if (!b) b = new_node(p, v);
	else t[b].v = t[b].s = v;
	i = merge(merge(a, b), c);
}

i64 query(int i, int l, int r) {
	if (i == null) return 0;
	if (l <= t[i].lx && t[i].rx <= r) return t[i].s;
	if (r < t[i].lx || t[i].rx < l) return 0;
	i64 ans = 0;
	if (l <= t[i].x && t[i].x <= r) ans = gcd(ans, t[i].v);
	if (l < t[i].x && t[i].ls) ans = gcd(ans, query(t[i].ls, l, r));
	if (r > t[i].x && t[i].rs) ans = gcd(ans, query(t[i].rs, l, r));
	return ans;
}

struct SegNode {
	int nd;
	SegNode *ls, *rs;
};

void change(int x, int y, i64 v, SegNode *&i, int a, int b) {
	if (!i) i = new SegNode{0, nullptr, nullptr};
	if (a + 1 == b) return change(i->nd, y, v);
	int m = (a + b) >> 1;
	if (x < m) change(x, y, v, i->ls, a, m);
	else change(x, y, v, i->rs, m, b);
	change(i->nd, y, gcd(i->ls ? query(i->ls->nd, y, y) : 0, i->rs ? query(i->rs->nd, y, y) : 0));
}

i64 query(int l, int r, int L, int R, SegNode *i, int a, int b) {
	if (!i) return 0;
	if (l <= a && b <= r) return query(i->nd, L, R);
	if (r <= a || b <= l) return 0;
	int m = (a + b) >> 1;
	return gcd(query(l, r, L, R, i->ls, a, m), query(l, r, L, R, i->rs, m, b));
}

int R, C;
SegNode *rt;

void init(int _R, int _C) {
	R = _R; C = _C;
	rt = nullptr;
}

void update(int P, int Q, i64 K) {
	change(P, Q, K, rt, 0, R);
}

i64 calculate(int P, int Q, int U, int V) {
	return query(P, U + 1, Q, V, rt, 0, R);
}

#ifdef DEBUG
#include "grader.c"
#endif

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 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 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 750 ms 6244 KB Output is correct
5 Correct 341 ms 6596 KB Output is correct
6 Correct 670 ms 3276 KB Output is correct
7 Correct 790 ms 3148 KB Output is correct
8 Correct 438 ms 2796 KB Output is correct
9 Correct 744 ms 3140 KB Output is correct
10 Correct 713 ms 2768 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 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 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 1075 ms 7992 KB Output is correct
13 Correct 1631 ms 3032 KB Output is correct
14 Correct 318 ms 836 KB Output is correct
15 Correct 1775 ms 3648 KB Output is correct
16 Correct 373 ms 5608 KB Output is correct
17 Correct 877 ms 4036 KB Output is correct
18 Correct 1833 ms 5972 KB Output is correct
19 Correct 1332 ms 6092 KB Output is correct
20 Correct 1318 ms 5520 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 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 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 764 ms 6236 KB Output is correct
13 Correct 341 ms 6596 KB Output is correct
14 Correct 700 ms 3284 KB Output is correct
15 Correct 816 ms 3092 KB Output is correct
16 Correct 445 ms 2880 KB Output is correct
17 Correct 744 ms 3204 KB Output is correct
18 Correct 772 ms 2824 KB Output is correct
19 Correct 1035 ms 7920 KB Output is correct
20 Correct 1714 ms 2940 KB Output is correct
21 Correct 352 ms 1012 KB Output is correct
22 Correct 1835 ms 3608 KB Output is correct
23 Correct 381 ms 5588 KB Output is correct
24 Correct 943 ms 3948 KB Output is correct
25 Correct 1683 ms 5872 KB Output is correct
26 Correct 1434 ms 6024 KB Output is correct
27 Correct 1297 ms 5504 KB Output is correct
28 Correct 641 ms 20904 KB Output is correct
29 Correct 1784 ms 23976 KB Output is correct
30 Correct 2119 ms 16904 KB Output is correct
31 Correct 2058 ms 13128 KB Output is correct
32 Correct 523 ms 856 KB Output is correct
33 Correct 744 ms 1220 KB Output is correct
34 Correct 461 ms 21072 KB Output is correct
35 Correct 1151 ms 11644 KB Output is correct
36 Correct 2747 ms 21500 KB Output is correct
37 Correct 2131 ms 21576 KB Output is correct
38 Correct 2017 ms 20956 KB Output is correct
39 Correct 1641 ms 16908 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 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 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 808 ms 6288 KB Output is correct
13 Correct 331 ms 6632 KB Output is correct
14 Correct 740 ms 3336 KB Output is correct
15 Correct 859 ms 3008 KB Output is correct
16 Correct 480 ms 2876 KB Output is correct
17 Correct 781 ms 3100 KB Output is correct
18 Correct 880 ms 2820 KB Output is correct
19 Correct 1262 ms 7952 KB Output is correct
20 Correct 1867 ms 3204 KB Output is correct
21 Correct 375 ms 836 KB Output is correct
22 Correct 1830 ms 3780 KB Output is correct
23 Correct 410 ms 5636 KB Output is correct
24 Correct 932 ms 4148 KB Output is correct
25 Correct 1593 ms 6140 KB Output is correct
26 Correct 1365 ms 6084 KB Output is correct
27 Correct 1289 ms 5496 KB Output is correct
28 Correct 580 ms 20924 KB Output is correct
29 Correct 1805 ms 23984 KB Output is correct
30 Correct 2317 ms 16864 KB Output is correct
31 Correct 1928 ms 13120 KB Output is correct
32 Correct 537 ms 924 KB Output is correct
33 Correct 785 ms 1256 KB Output is correct
34 Correct 455 ms 21108 KB Output is correct
35 Correct 1159 ms 11712 KB Output is correct
36 Correct 2833 ms 21512 KB Output is correct
37 Correct 2004 ms 21572 KB Output is correct
38 Correct 2262 ms 20920 KB Output is correct
39 Correct 881 ms 44348 KB Output is correct
40 Correct 3220 ms 56884 KB Output is correct
41 Correct 3449 ms 42776 KB Output is correct
42 Correct 3170 ms 34116 KB Output is correct
43 Correct 1067 ms 51564 KB Output is correct
44 Correct 905 ms 10552 KB Output is correct
45 Correct 1805 ms 27172 KB Output is correct
46 Correct 3878 ms 55820 KB Output is correct
47 Correct 3996 ms 55732 KB Output is correct
48 Correct 3868 ms 55228 KB Output is correct
49 Correct 1 ms 204 KB Output is correct