oj.uz

Submission #595734

# Submission time Handle Problem Language Result Execution time Memory
595734 2022-07-14T04:54:57 Z Bobaa Game (IOI13_game) C++17
100 / 100
 2888 ms 73268 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std; 

mt19937 rng(time(0)); 

struct TreapNode {
	TreapNode *l, *r; 
	int pos, key, mn, mx; 
	long long val, g; 
	
	TreapNode(int position, long long 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; 
	}
	
	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) return r; 
		if (!r) return l;
		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, long long value) {
		if (t -> pos == pos) {
			t -> val = value; 
			t -> update(); 
			return; 
		}
		if (t -> pos > pos) update(t -> l, pos, value); 
		else update(t -> r, pos, value); 
		t -> update(); 
	}
	
	void insert(int pos, long long value) {
		if (find(pos)) {
			update(root, pos, value); 
			return; 
		}
		TreapNode *l, *r; 
		split(root, pos, l, r); 
		root = merge(merge(l, new TreapNode(pos, value)), r); 
	}
	
	long long query(TreapNode *t, int l, int r) {
		if (t -> mx < l || t -> mn > r) return 0LL; 
		if (l <= t -> mn && t -> mx <= r) return t -> g; 
		long long res = 0; 
		if (l <= t -> pos && t -> pos <= r) res = t -> val; 
		if (t -> l) res = __gcd(res, query(t -> l, l, r)); 
		if (t -> r) res = __gcd(res, query(t -> r, l, r)); 
		return res; 
	}
	
	long long query(int l, int r) {
		if (!root) return 0LL; 
		return query(root, l, r); 
	}
}; 

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) {
		long long 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, long long val) {
		if (hi < x || lo > x) return; 
		if (lo == hi) {
			treap.insert(y, val); 
			return; 
		}
		int mid = (lo + hi) / 2; 
		if (x <= mid) {
			new_left(); 
			l -> update(x, y, val); 
		} else {
			new_right(); 
			r -> update(x, y, val); 
		}
		fix(y); 
	}
	
	long long query(int t, int b, int st, int en) {
		if (hi < t || lo > b) return 0LL; 
		if (t <= lo && hi <= b) return treap.query(st, en); 
		long long 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) {
	segtree = SegTree(0, R - 1); 
}

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

long long 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 1 ms 340 KB Output is correct
4 Correct 1 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 292 KB Output is correct
11 Correct 2 ms 260 KB Output is correct
12 Correct 1 ms 308 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 449 ms 11412 KB Output is correct
5 Correct 248 ms 11236 KB Output is correct
6 Correct 541 ms 8644 KB Output is correct
7 Correct 584 ms 8468 KB Output is correct
8 Correct 341 ms 7352 KB Output is correct
9 Correct 557 ms 8456 KB Output is correct
10 Correct 590 ms 8180 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 1 ms 308 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 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 300 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 340 KB Output is correct
10 Correct 1 ms 260 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 655 ms 13308 KB Output is correct
13 Correct 1098 ms 7700 KB Output is correct
14 Correct 232 ms 5596 KB Output is correct
15 Correct 1149 ms 9096 KB Output is correct
16 Correct 271 ms 11408 KB Output is correct
17 Correct 738 ms 9752 KB Output is correct
18 Correct 1393 ms 12844 KB Output is correct
19 Correct 1063 ms 12892 KB Output is correct
20 Correct 1063 ms 12336 KB Output is correct
21 Correct 1 ms 212 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 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 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 456 ms 11400 KB Output is correct
13 Correct 243 ms 11156 KB Output is correct
14 Correct 522 ms 8592 KB Output is correct
15 Correct 609 ms 8328 KB Output is correct
16 Correct 342 ms 7368 KB Output is correct
17 Correct 524 ms 8416 KB Output is correct
18 Correct 512 ms 8080 KB Output is correct
19 Correct 712 ms 13224 KB Output is correct
20 Correct 1158 ms 7568 KB Output is correct
21 Correct 226 ms 5508 KB Output is correct
22 Correct 1147 ms 8984 KB Output is correct
23 Correct 267 ms 11436 KB Output is correct
24 Correct 740 ms 9732 KB Output is correct
25 Correct 1330 ms 12912 KB Output is correct
26 Correct 1163 ms 13100 KB Output is correct
27 Correct 1018 ms 12480 KB Output is correct
28 Correct 411 ms 39172 KB Output is correct
29 Correct 1135 ms 41720 KB Output is correct
30 Correct 1381 ms 29832 KB Output is correct
31 Correct 1274 ms 24704 KB Output is correct
32 Correct 289 ms 10168 KB Output is correct
33 Correct 431 ms 10592 KB Output is correct
34 Correct 363 ms 35496 KB Output is correct
35 Correct 951 ms 25348 KB Output is correct
36 Correct 1935 ms 39704 KB Output is correct
37 Correct 1536 ms 39748 KB Output is correct
38 Correct 1499 ms 39140 KB Output is correct
39 Correct 1257 ms 33012 KB Output is correct
40 Correct 1 ms 212 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 300 KB Output is correct
3 Correct 1 ms 340 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 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 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 488 ms 11400 KB Output is correct
13 Correct 231 ms 11140 KB Output is correct
14 Correct 573 ms 8652 KB Output is correct
15 Correct 620 ms 8364 KB Output is correct
16 Correct 341 ms 7408 KB Output is correct
17 Correct 562 ms 8448 KB Output is correct
18 Correct 545 ms 8100 KB Output is correct
19 Correct 650 ms 13264 KB Output is correct
20 Correct 1174 ms 7688 KB Output is correct
21 Correct 208 ms 5524 KB Output is correct
22 Correct 1136 ms 9004 KB Output is correct
23 Correct 262 ms 11340 KB Output is correct
24 Correct 749 ms 9716 KB Output is correct
25 Correct 1330 ms 12892 KB Output is correct
26 Correct 1121 ms 12960 KB Output is correct
27 Correct 1070 ms 12288 KB Output is correct
28 Correct 431 ms 39056 KB Output is correct
29 Correct 1205 ms 41676 KB Output is correct
30 Correct 1484 ms 29808 KB Output is correct
31 Correct 1201 ms 24632 KB Output is correct
32 Correct 312 ms 10088 KB Output is correct
33 Correct 413 ms 10580 KB Output is correct
34 Correct 341 ms 35360 KB Output is correct
35 Correct 1018 ms 25296 KB Output is correct
36 Correct 2009 ms 39668 KB Output is correct
37 Correct 1619 ms 39812 KB Output is correct
38 Correct 1684 ms 39192 KB Output is correct
39 Correct 689 ms 71172 KB Output is correct
40 Correct 2313 ms 73268 KB Output is correct
41 Correct 2573 ms 55164 KB Output is correct
42 Correct 2009 ms 43628 KB Output is correct
43 Correct 712 ms 67904 KB Output is correct
44 Correct 386 ms 10664 KB Output is correct
45 Correct 1324 ms 33056 KB Output is correct
46 Correct 2848 ms 72024 KB Output is correct
47 Correct 2888 ms 72072 KB Output is correct
48 Correct 2701 ms 71684 KB Output is correct
49 Correct 1 ms 304 KB Output is correct