oj.uz

Submission #561416

# Submission time Handle Problem Language Result Execution time Memory
561416 2022-05-12T19:20:11 Z stefantaga Game (IOI13_game) C++14
100 / 100
 3377 ms 73376 KB 
#include "game.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll gcd(ll x, ll y) { return !y ? x : gcd(y, x % y); }
int rnd() { return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15)); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct TreapNode {
	TreapNode *l, *r;
	int pos, key, mn, mx;
	ll val, g;

	TreapNode(int position, ll value) {
		l = r = nullptr;
		mn = mx = pos = position;
		key = rng();
		val = g = value;
	}

	void update() {
		g = val;
		if (l) g = gcd(g, l->g);
		if (r) g = gcd(g, r->g);
		mn = (l ? l->mn : pos);
		mx = (r ? r->mx : pos);
	}
};

struct Treap {
	TreapNode *root;

	Treap() {
		root = nullptr;
		srand(rnd());
	}

	void split(TreapNode *t, int pos, TreapNode *&l, TreapNode *&r) {
		if (t == nullptr) {
			l = r = nullptr;
			return;
		}
		if (t->pos < pos) {
			split(t->r, pos, l, r);
			t->r = l;
			l = t;
		} else {
			split(t->l, pos, l, r);
			t->l = r;
			r = t;
		}
		t->update();
	}

	TreapNode* merge(TreapNode *l, TreapNode *r) {
		if (!l || !r) return l ? l : r;
		if (l->key < r->key) {
			l->r = merge(l->r, r);
			l->update();
			return l;
		} else {
			r->l = merge(l, r->l);
			r->update();
			return r;
		}
	}

	bool find(int pos) {
		TreapNode *t = root;
		while (t) {
			if (t->pos == pos) return true;
			if (t->pos > pos) t = t->l;
			else t = t->r;
		}
		return false;
	}

	void update(TreapNode *t, int pos, ll val) {
		if (t->pos == pos) {
			t->val = val;
			t->update();
			return;
		}
		if (t->pos > pos) update(t->l, pos, val);
		else update(t->r, pos, val);
		t->update();
	}

	void insert(int pos, ll val) {
		if (find(pos)) update(root, pos, val);
		else {
			TreapNode *l, *r;
			split(root, pos, l, r);
			root = merge(merge(l, new TreapNode(pos, val)), r);
		}
	}

	ll query(TreapNode *t, int st, int en) {
		if (t->mx < st || en < t->mn) return 0;
		if (st <= t->mn && t->mx <= en) return t->g;

		ll ans = (st <= t->pos && t->pos <= en ? t->val : 0);
		if (t->l) ans = gcd(ans, query(t->l, st, en));
		if (t->r) ans = gcd(ans, query(t->r, st, en));
		return ans;
	}
	ll query(int st, int en) {
		if (!root) return 0;
		return query(root, st, en);
	}
};

struct Segtree {
	Segtree *l, *r;
	Treap treap;
	int lo, hi;

	Segtree() { l = r = nullptr; }
	Segtree(int st, int en) {
		l = r = nullptr;
		lo = st, hi = en;
	}

	void new_left() {
		if (!l) l = new Segtree(lo, (lo + hi) / 2);
	}
	void new_right() {
		if (!r) r = new Segtree((lo + hi) / 2 + 1, hi);
	}
	void fix(int pos) {
		ll val = 0;
		if (l) val = gcd(val, l->treap.query(pos, pos));
		if (r) val = gcd(val, r->treap.query(pos, pos));
		treap.insert(pos, val);
	}

	void update(int x, int y, ll val) {
		if (hi < x || x < lo) return;
		if (lo == hi) {
			treap.insert(y, val);
			return;
		}

		if (x <= (lo + hi) / 2) {
			new_left();
			l->update(x, y, val);
		} else {
			new_right();
			r->update(x, y, val);
		}
		fix(y);
	}

	ll query(int t, int b, int st, int en) {
		if (hi < t || b < lo) return 0;
		if (t <= lo && hi <= b) return treap.query(st, en);

		ll ans = 0;
		if (l) ans = gcd(ans, l->query(t, b, st, en));
		if (r) ans = gcd(ans, r->query(t, b, st, en));
		return ans;
	}
};

Segtree segtree;

void init(int R, int C) {
	srand(12341234);
	segtree = Segtree(0, R - 1);
}

void update(int P, int Q, ll K) { segtree.update(P, Q, K); }

ll calculate(int P, int Q, int U, int V) {
	return segtree.query(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 503 ms 11380 KB Output is correct
5 Correct 253 ms 11176 KB Output is correct
6 Correct 600 ms 8636 KB Output is correct
7 Correct 623 ms 8428 KB Output is correct
8 Correct 361 ms 7388 KB Output is correct
9 Correct 543 ms 8544 KB Output is correct
10 Correct 524 ms 8136 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 667 ms 13308 KB Output is correct
13 Correct 1051 ms 7744 KB Output is correct
14 Correct 218 ms 5596 KB Output is correct
15 Correct 1169 ms 8992 KB Output is correct
16 Correct 253 ms 11468 KB Output is correct
17 Correct 716 ms 9664 KB Output is correct
18 Correct 1352 ms 12968 KB Output is correct
19 Correct 1076 ms 13028 KB Output is correct
20 Correct 985 ms 12396 KB Output is correct
21 Correct 1 ms 260 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 477 ms 11424 KB Output is correct
13 Correct 241 ms 11236 KB Output is correct
14 Correct 503 ms 8668 KB Output is correct
15 Correct 572 ms 8412 KB Output is correct
16 Correct 337 ms 7372 KB Output is correct
17 Correct 543 ms 8464 KB Output is correct
18 Correct 497 ms 8132 KB Output is correct
19 Correct 650 ms 13380 KB Output is correct
20 Correct 1096 ms 7692 KB Output is correct
21 Correct 206 ms 5580 KB Output is correct
22 Correct 1096 ms 9024 KB Output is correct
23 Correct 243 ms 11332 KB Output is correct
24 Correct 706 ms 9656 KB Output is correct
25 Correct 1214 ms 12916 KB Output is correct
26 Correct 1032 ms 13072 KB Output is correct
27 Correct 978 ms 12340 KB Output is correct
28 Correct 701 ms 39000 KB Output is correct
29 Correct 1373 ms 41636 KB Output is correct
30 Correct 1535 ms 29868 KB Output is correct
31 Correct 1395 ms 24648 KB Output is correct
32 Correct 296 ms 10208 KB Output is correct
33 Correct 422 ms 10552 KB Output is correct
34 Correct 629 ms 35532 KB Output is correct
35 Correct 1057 ms 25452 KB Output is correct
36 Correct 2069 ms 39740 KB Output is correct
37 Correct 1779 ms 39812 KB Output is correct
38 Correct 1755 ms 39244 KB Output is correct
39 Correct 1422 ms 33068 KB Output is correct
40 Correct 1 ms 304 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 501 ms 11480 KB Output is correct
13 Correct 240 ms 11212 KB Output is correct
14 Correct 498 ms 8748 KB Output is correct
15 Correct 569 ms 8340 KB Output is correct
16 Correct 344 ms 7524 KB Output is correct
17 Correct 533 ms 8512 KB Output is correct
18 Correct 519 ms 8088 KB Output is correct
19 Correct 654 ms 13268 KB Output is correct
20 Correct 1077 ms 7724 KB Output is correct
21 Correct 210 ms 5624 KB Output is correct
22 Correct 1151 ms 9088 KB Output is correct
23 Correct 255 ms 11488 KB Output is correct
24 Correct 704 ms 9724 KB Output is correct
25 Correct 1223 ms 13036 KB Output is correct
26 Correct 1026 ms 13048 KB Output is correct
27 Correct 1010 ms 12424 KB Output is correct
28 Correct 707 ms 39004 KB Output is correct
29 Correct 1455 ms 41856 KB Output is correct
30 Correct 1547 ms 29828 KB Output is correct
31 Correct 1352 ms 24576 KB Output is correct
32 Correct 286 ms 10276 KB Output is correct
33 Correct 408 ms 10484 KB Output is correct
34 Correct 640 ms 35668 KB Output is correct
35 Correct 1053 ms 25344 KB Output is correct
36 Correct 2183 ms 39688 KB Output is correct
37 Correct 1788 ms 40092 KB Output is correct
38 Correct 1757 ms 39300 KB Output is correct
39 Correct 1197 ms 71260 KB Output is correct
40 Correct 2626 ms 73376 KB Output is correct
41 Correct 2514 ms 55476 KB Output is correct
42 Correct 2165 ms 43824 KB Output is correct
43 Correct 1341 ms 68092 KB Output is correct
44 Correct 396 ms 10792 KB Output is correct
45 Correct 1428 ms 32992 KB Output is correct
46 Correct 3377 ms 72240 KB Output is correct
47 Correct 3328 ms 72332 KB Output is correct
48 Correct 3243 ms 71816 KB Output is correct
49 Correct 1 ms 216 KB Output is correct