oj.uz

Submission #417972

# Submission time Handle Problem Language Result Execution time Memory
417972 2021-06-04T17:34:57 Z Mlxa Game (IOI13_game) C++14
100 / 100
 7549 ms 39244 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "game.h"

ll gcd(ll x, ll y) {
	ll tmp;
	while (x != y && y != 0) {
		tmp = x;
		x = y;
		y = tmp % y;
	}
	return x;
}

const int TREAP_NODES = 1e6;

mt19937 rnd;

namespace dd {
struct treap {
	int ls, rs, ke, pr;
	ll va, gc;
} pool[TREAP_NODES];
int treap_ff = 1;
#define gt(x,type) type &x(int v) { assert(0 <= v && v < TREAP_NODES); return pool[v].x; }
gt(ls,int) gt(rs,int) gt(ke,int) gt(pr,int) gt(va,ll) gt(gc,ll)
#undef gt

int new_node(int x, ll q) {
	int v = treap_ff++;
	ls(v) = rs(v) = 0;
	ke(v) = x;
	pr(v) = (int)rnd();
	va(v) = gc(v) = q;
	return v;
}

int pull(int v) {
	gc(v) = gcd(va(v), gcd(gc(ls(v)), gc(rs(v))));
	return v;
}

int merge(int l, int r) {
	if (!l) {
		return r;
	}
	if (!r) {
		return l;
	}
	if (pr(l) < pr(r)) {
		rs(l) = merge(rs(l), r);
		return pull(l);
	} else {
		ls(r) = merge(l, ls(r));
		return pull(r);
	}
}

pair<int, int> split(int t, int x) {
	if (!t) {
		return {t, t};
	}
	int l, r;
	if (x < ke(t)) {
		tie(l, ls(t)) = split(ls(t), x);
		r = pull(t);
	} else {
		tie(rs(t), r) = split(rs(t), x);
		l = pull(t);
	}
	return {l, r};
}

ll query(int t, int ql, int qr) {
	int tl, tm, tr;
	tie(tl, tm) = split(t, ql - 1);
	tie(tm, tr) = split(tm, qr - 1);
	ll res = gc(tm);
	int nt = merge(merge(tl, tm), tr);
	assert(t == nt);
	return res;
}

__attribute__((warn_unused_result))
int upd(int t, int pos, ll val) {
	int tl, tm, tr;
	tie(tl, tm) = split(t, pos - 1);
	tie(tm, tr) = split(tm, pos);
	if (tm) {
		assert(!ls(tm) && !rs(tm));
		assert(ke(tm) == pos);
		va(tm) = gc(tm) = val;
	} else {
		tm = new_node(pos, val);
	}
	return merge(merge(tl, tm), tr);
}

void print(int t, int h = 0) {
	if (t) {
		print(ls(t), h + 1);
		cout << ke(t) << ":" << va(t) << " ";
		print(rs(t), h + 1);
	}
	if (!h) {
		cout << endl;
	}
}
}

const int ST_NODES = 1e6;
const int RANGE    = 1e9 + 10;
struct node {
	int ls, rs, tr;
} pool[ST_NODES];
int ff_st = 1;

#define gt(x,type) type &x(int v) { assert(0 <= v && v < ST_NODES); return pool[v].x; }
gt(ls,int) gt(rs,int) gt(tr,int)
#undef gt

int new_node() {
	int v = ff_st++;
	ls(v) = rs(v) = tr(v) = 0;
	return v;
}

ll query(int v, int vl, int vr, int ql, int qr, int yl, int yr) {
	if (!v || qr <= vl || vr <= ql) {
		return 0;
	}
	if (ql <= vl && vr <= qr) {
		return dd::query(tr(v), yl, yr);
	}
	int vm = (vl + vr) / 2;
	return gcd(query(ls(v), vl, vm, ql, qr, yl, yr), query(rs(v), vm, vr, ql, qr, yl, yr));
}

__attribute__((warn_unused_result))
int upd(int v, int vl, int vr, int x, int y, ll to) {
	assert(vl <= x && x < vr);
	if (!v) {
		v = new_node();
	}
	if (vr - vl == 1) {
		tr(v) = dd::upd(tr(v), y, to);
		return v;
	}
	int vm = (vl + vr) / 2;
	if (x < vm) {
		ls(v) = upd(ls(v), vl, vm, x, y, to);
		ll nval = dd::query(tr(rs(v)), y, y + 1);
		nval = gcd(nval, dd::query(tr(ls(v)), y, y + 1));
		nval = gcd(nval, to);
		tr(v) = dd::upd(tr(v), y, nval);
	} else {
		rs(v) = upd(rs(v), vm, vr, x, y, to);
		ll nval = dd::query(tr(ls(v)), y, y + 1);
		nval = gcd(nval, dd::query(tr(rs(v)), y, y + 1));
		nval = gcd(nval, to);
		tr(v) = dd::upd(tr(v), y, nval);
	}
	return v;
}

void init(int r, int c) {
	(void)r; (void)c;
}

int root = 0;

void dfs(int v, int vl, int vr) {
	if (!v) {
		return;
	}
	cout << "#\t" << vl << " " << vr << endl;
	dd::print(tr(v));
	int vm = (vl + vr) / 2;
	dfs(ls(v), vl, vm);
	dfs(rs(v), vm, vr);
}
 
void update(int p, int q, ll k) {
	root = upd(root, 0, RANGE, p, q, k);
	// dfs(root, 0, RANGE);
}
 
ll calculate(int p, int q, int u, int v) {
	return query(root, 0, RANGE, p, u + 1, q, v + 1);
}
 
#ifdef LC
#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 6 ms 332 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 5 ms 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 2 ms 308 KB Output is correct
11 Correct 2 ms 332 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 2100 ms 13536 KB Output is correct
5 Correct 1362 ms 13736 KB Output is correct
6 Correct 2866 ms 15160 KB Output is correct
7 Correct 2909 ms 14916 KB Output is correct
8 Correct 1718 ms 10604 KB Output is correct
9 Correct 2909 ms 15132 KB Output is correct
10 Correct 2458 ms 14752 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 6 ms 332 KB Output is correct
3 Correct 6 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 6 ms 332 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 2103 ms 11612 KB Output is correct
13 Correct 3652 ms 6840 KB Output is correct
14 Correct 802 ms 5548 KB Output is correct
15 Correct 4030 ms 8400 KB Output is correct
16 Correct 1257 ms 9652 KB Output is correct
17 Correct 2473 ms 9136 KB Output is correct
18 Correct 4431 ms 10812 KB Output is correct
19 Correct 3837 ms 11188 KB Output is correct
20 Correct 3323 ms 10576 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 6 ms 332 KB Output is correct
3 Correct 6 ms 380 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2102 ms 17880 KB Output is correct
13 Correct 1313 ms 17764 KB Output is correct
14 Correct 2738 ms 15192 KB Output is correct
15 Correct 2852 ms 15252 KB Output is correct
16 Correct 1659 ms 10856 KB Output is correct
17 Correct 2875 ms 15012 KB Output is correct
18 Correct 2406 ms 14964 KB Output is correct
19 Correct 1988 ms 11516 KB Output is correct
20 Correct 3518 ms 7120 KB Output is correct
21 Correct 789 ms 5724 KB Output is correct
22 Correct 3988 ms 8352 KB Output is correct
23 Correct 1314 ms 9488 KB Output is correct
24 Correct 2456 ms 9236 KB Output is correct
25 Correct 4168 ms 10940 KB Output is correct
26 Correct 3734 ms 10952 KB Output is correct
27 Correct 3239 ms 10400 KB Output is correct
28 Correct 1094 ms 23296 KB Output is correct
29 Correct 2371 ms 25892 KB Output is correct
30 Correct 4823 ms 17764 KB Output is correct
31 Correct 4583 ms 15320 KB Output is correct
32 Correct 738 ms 10176 KB Output is correct
33 Correct 1098 ms 10480 KB Output is correct
34 Correct 2066 ms 19472 KB Output is correct
35 Correct 2312 ms 17268 KB Output is correct
36 Correct 4455 ms 23700 KB Output is correct
37 Correct 3538 ms 23928 KB Output is correct
38 Correct 3491 ms 23216 KB Output is correct
39 Correct 3019 ms 20752 KB Output is correct
40 Correct 1 ms 332 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 6 ms 364 KB Output is correct
3 Correct 6 ms 308 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 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 4 ms 332 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2097 ms 17916 KB Output is correct
13 Correct 1380 ms 17820 KB Output is correct
14 Correct 2754 ms 15140 KB Output is correct
15 Correct 2867 ms 15028 KB Output is correct
16 Correct 1643 ms 10756 KB Output is correct
17 Correct 2817 ms 15228 KB Output is correct
18 Correct 2386 ms 14748 KB Output is correct
19 Correct 1971 ms 11720 KB Output is correct
20 Correct 3510 ms 7008 KB Output is correct
21 Correct 788 ms 5788 KB Output is correct
22 Correct 4006 ms 8500 KB Output is correct
23 Correct 1249 ms 9484 KB Output is correct
24 Correct 2455 ms 9080 KB Output is correct
25 Correct 4162 ms 10916 KB Output is correct
26 Correct 3747 ms 11048 KB Output is correct
27 Correct 3260 ms 10412 KB Output is correct
28 Correct 1103 ms 23116 KB Output is correct
29 Correct 2357 ms 25868 KB Output is correct
30 Correct 4829 ms 17788 KB Output is correct
31 Correct 4442 ms 15364 KB Output is correct
32 Correct 738 ms 10088 KB Output is correct
33 Correct 1088 ms 10340 KB Output is correct
34 Correct 2048 ms 19576 KB Output is correct
35 Correct 2257 ms 17476 KB Output is correct
36 Correct 4120 ms 23816 KB Output is correct
37 Correct 3465 ms 24164 KB Output is correct
38 Correct 3296 ms 23304 KB Output is correct
39 Correct 1612 ms 37004 KB Output is correct
40 Correct 4109 ms 39244 KB Output is correct
41 Correct 7549 ms 29528 KB Output is correct
42 Correct 6628 ms 24092 KB Output is correct
43 Correct 2938 ms 33888 KB Output is correct
44 Correct 1185 ms 10556 KB Output is correct
45 Correct 2931 ms 20728 KB Output is correct
46 Correct 5953 ms 38064 KB Output is correct
47 Correct 6007 ms 37824 KB Output is correct
48 Correct 5503 ms 37524 KB Output is correct
49 Correct 1 ms 204 KB Output is correct