oj.uz

Submission #1104888

# Submission time Handle Problem Language Result Execution time Memory
1104888 2024-10-24T15:46:54 Z spycoderyt Game (IOI13_game) C++17
100 / 100
 2797 ms 73404 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)); }

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 = rnd();
		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 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 436 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 319 ms 10824 KB Output is correct
5 Correct 156 ms 11080 KB Output is correct
6 Correct 350 ms 8632 KB Output is correct
7 Correct 435 ms 8444 KB Output is correct
8 Correct 257 ms 7432 KB Output is correct
9 Correct 420 ms 8108 KB Output is correct
10 Correct 390 ms 7476 KB Output is correct
11 Correct 1 ms 336 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 440 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 536 ms 13384 KB Output is correct
13 Correct 703 ms 7752 KB Output is correct
14 Correct 150 ms 5704 KB Output is correct
15 Correct 768 ms 9192 KB Output is correct
16 Correct 185 ms 11340 KB Output is correct
17 Correct 593 ms 8436 KB Output is correct
18 Correct 1012 ms 12912 KB Output is correct
19 Correct 902 ms 12856 KB Output is correct
20 Correct 760 ms 12372 KB Output is correct
21 Correct 1 ms 336 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 320 ms 11540 KB Output is correct
13 Correct 157 ms 11336 KB Output is correct
14 Correct 375 ms 8776 KB Output is correct
15 Correct 475 ms 8444 KB Output is correct
16 Correct 272 ms 7224 KB Output is correct
17 Correct 437 ms 8520 KB Output is correct
18 Correct 393 ms 7608 KB Output is correct
19 Correct 508 ms 13128 KB Output is correct
20 Correct 713 ms 7952 KB Output is correct
21 Correct 143 ms 4936 KB Output is correct
22 Correct 764 ms 9060 KB Output is correct
23 Correct 186 ms 11004 KB Output is correct
24 Correct 607 ms 9804 KB Output is correct
25 Correct 1020 ms 12708 KB Output is correct
26 Correct 890 ms 13016 KB Output is correct
27 Correct 804 ms 12104 KB Output is correct
28 Correct 613 ms 38984 KB Output is correct
29 Correct 1091 ms 41544 KB Output is correct
30 Correct 1070 ms 29952 KB Output is correct
31 Correct 991 ms 24604 KB Output is correct
32 Correct 207 ms 10056 KB Output is correct
33 Correct 310 ms 10580 KB Output is correct
34 Correct 608 ms 35616 KB Output is correct
35 Correct 944 ms 25416 KB Output is correct
36 Correct 1787 ms 39544 KB Output is correct
37 Correct 1490 ms 39808 KB Output is correct
38 Correct 1426 ms 39240 KB Output is correct
39 Correct 1135 ms 33096 KB Output is correct
40 Correct 1 ms 336 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 345 ms 11328 KB Output is correct
13 Correct 171 ms 11080 KB Output is correct
14 Correct 372 ms 8264 KB Output is correct
15 Correct 450 ms 8008 KB Output is correct
16 Correct 253 ms 6732 KB Output is correct
17 Correct 411 ms 8276 KB Output is correct
18 Correct 410 ms 8264 KB Output is correct
19 Correct 510 ms 13244 KB Output is correct
20 Correct 678 ms 7016 KB Output is correct
21 Correct 140 ms 5192 KB Output is correct
22 Correct 737 ms 8524 KB Output is correct
23 Correct 189 ms 11080 KB Output is correct
24 Correct 590 ms 9168 KB Output is correct
25 Correct 1026 ms 12872 KB Output is correct
26 Correct 825 ms 12568 KB Output is correct
27 Correct 758 ms 11720 KB Output is correct
28 Correct 606 ms 38992 KB Output is correct
29 Correct 1142 ms 41760 KB Output is correct
30 Correct 1095 ms 29692 KB Output is correct
31 Correct 949 ms 24648 KB Output is correct
32 Correct 201 ms 10312 KB Output is correct
33 Correct 301 ms 10568 KB Output is correct
34 Correct 592 ms 35388 KB Output is correct
35 Correct 905 ms 25416 KB Output is correct
36 Correct 1733 ms 39752 KB Output is correct
37 Correct 1529 ms 39840 KB Output is correct
38 Correct 1517 ms 39276 KB Output is correct
39 Correct 1161 ms 71240 KB Output is correct
40 Correct 2114 ms 73404 KB Output is correct
41 Correct 1872 ms 55324 KB Output is correct
42 Correct 1625 ms 43592 KB Output is correct
43 Correct 1282 ms 67904 KB Output is correct
44 Correct 293 ms 10752 KB Output is correct
45 Correct 1233 ms 33104 KB Output is correct
46 Correct 2797 ms 72156 KB Output is correct
47 Correct 2498 ms 72008 KB Output is correct
48 Correct 2764 ms 71824 KB Output is correct
49 Correct 1 ms 336 KB Output is correct