oj.uz

Submission #375930

# Submission time Handle Problem Language Result Execution time Memory
375930 2021-03-10T09:38:52 Z vot808 Game (IOI13_game) C++17
100 / 100
 3708 ms 117580 KB 
#include "bits/stdc++.h"
#include "game.h"
#ifdef mlocal
#include "grader.c"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'
 
int MXR, MXC;

struct SegmentTree {
	public:
	vector<ii> c;
	vi l, r;
	vector<ll> tree;
	int pt = 1;
	
	void update(int &i, ll &val, int p) {
		if (l[p] == r[p]) {
			tree[p] = val;
			return;
		}
		
		int mid = (l[p]+r[p])/2, s = i > mid;
		if (!c[p][s]) {
			// Key memory heuristic: if no child in this direction, then ONLY create the leaf node and NOT all intervals
			tree.resize(pt+1); c.resize(pt+1); l.push_back(i); r.push_back(i);
			c[p][s] = pt++;
		} else if (l[c[p][s]] > i or r[c[p][s]] < i) {
			// If there already exists a node in this direction and this is not the interval we need, 
			// then find the last interval such that this existing node and the new leaf node lie in different sides.
			// It then reduces to the previous case for this newly create interval node.
			
			int cl = l[p], cr = r[p], cmid = (cl+cr)/2;
			while (!((r[c[p][s]] <= cmid) ^ (i <= cmid))) {
				if (i <= cmid) cr = cmid;
				else cl = cmid+1;
				cmid = (cl+cr)/2;
			}
			
			tree.resize(pt+1); c.resize(pt+1); l.push_back(cl); r.push_back(cr);
			c[pt][r[c[p][s]] > cmid] = c[p][s];
			c[p][s] = pt++;
		}
		
		update(i, val, c[p][s]);
		tree[p] = __gcd(c[p][0] ? tree[c[p][0]] : 0, c[p][1] ? tree[c[p][1]] : 0);
	}
	
	ll query(int &i, int &j, int p) {
		if (l[p] > j or r[p] < i) return 0;
		if (l[p] >= i and r[p] <= j) return tree[p];
		
		return __gcd(c[p][0] ? query(i, j, c[p][0]) : 0, c[p][1] ? query(i, j, c[p][1]) : 0);
	}
	
	SegmentTree() {
		c.resize(1); tree.resize(1); l.push_back(0); r.push_back(MXC);
	}
};
 
struct SegmentTree2D {
	public:
	vector<ii> c;
	vector<SegmentTree> tree;
	int pt = 1;
	
	void update(int &i, int &j, ll &val, int l, int r, int p) {
		if (l != r) {
			int mid = (l+r)/2, s = i > mid;
			if (!c[p][s]) {
				tree.resize(pt+1); c.resize(pt+1);
				c[p][s] = pt++;
			}
			
			update(i, j, val, s ? mid+1 : l, s ? r : mid, c[p][s]);
		}
		
		if (l != r) val = __gcd(c[p][0] ? tree[c[p][0]].query(j, j, 0) : 0, c[p][1] ? tree[c[p][1]].query(j, j, 0) : 0);
		
		tree[p].update(j, val, 0);
	}
	
	ll query(int &xi, int &xj, int &yi, int &yj, int l, int r, int p) {
		if (l > xj or r < xi) return 0;
		if (l >= xi and r <= xj) return tree[p].query(yi, yj, 0);
		
		int mid = (l+r)/2;
		return __gcd(c[p][0] ? query(xi, xj, yi, yj, l, mid, c[p][0]) : 0, c[p][1] ? query(xi, xj, yi, yj, mid+1, r, c[p][1]) : 0);
	}
	
	SegmentTree2D() {
		c.resize(1); tree.resize(1);
	}
};
 
SegmentTree2D tree;
 
void init(int R, int C) {
	// Wait, do I even need to do something here? :)
	MXR = R, MXC = C;
}
 
void update(int P, int Q, ll K) {
	tree.update(P, Q, K, 0, MXR, 0);
}
 
ll calculate(int P, int Q, int U, int V) {
	return tree.query(P, U, Q, V, 0, MXR, 0);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 541 ms 7660 KB Output is correct
5 Correct 416 ms 7660 KB Output is correct
6 Correct 534 ms 3948 KB Output is correct
7 Correct 543 ms 3820 KB Output is correct
8 Correct 358 ms 3564 KB Output is correct
9 Correct 521 ms 4012 KB Output is correct
10 Correct 506 ms 3452 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 372 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 970 ms 10976 KB Output is correct
13 Correct 1635 ms 4792 KB Output is correct
14 Correct 272 ms 1644 KB Output is correct
15 Correct 1757 ms 5792 KB Output is correct
16 Correct 714 ms 8968 KB Output is correct
17 Correct 760 ms 6040 KB Output is correct
18 Correct 1281 ms 9144 KB Output is correct
19 Correct 1099 ms 9436 KB Output is correct
20 Correct 1012 ms 8984 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 607 ms 7788 KB Output is correct
13 Correct 422 ms 7684 KB Output is correct
14 Correct 479 ms 4144 KB Output is correct
15 Correct 535 ms 3840 KB Output is correct
16 Correct 350 ms 3436 KB Output is correct
17 Correct 515 ms 3760 KB Output is correct
18 Correct 484 ms 3308 KB Output is correct
19 Correct 968 ms 10624 KB Output is correct
20 Correct 1662 ms 4896 KB Output is correct
21 Correct 274 ms 1388 KB Output is correct
22 Correct 1786 ms 5760 KB Output is correct
23 Correct 691 ms 8744 KB Output is correct
24 Correct 720 ms 6204 KB Output is correct
25 Correct 1391 ms 9112 KB Output is correct
26 Correct 1103 ms 9368 KB Output is correct
27 Correct 990 ms 8612 KB Output is correct
28 Correct 756 ms 51676 KB Output is correct
29 Correct 1625 ms 55132 KB Output is correct
30 Correct 2529 ms 36484 KB Output is correct
31 Correct 2372 ms 30052 KB Output is correct
32 Correct 383 ms 1904 KB Output is correct
33 Correct 519 ms 2584 KB Output is correct
34 Correct 1020 ms 52740 KB Output is correct
35 Correct 1116 ms 28432 KB Output is correct
36 Correct 2158 ms 52700 KB Output is correct
37 Correct 1731 ms 52872 KB Output is correct
38 Correct 1678 ms 52228 KB Output is correct
39 Correct 1466 ms 52172 KB Output is correct
40 Correct 1 ms 492 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 557 ms 7788 KB Output is correct
13 Correct 417 ms 8428 KB Output is correct
14 Correct 478 ms 4808 KB Output is correct
15 Correct 534 ms 5116 KB Output is correct
16 Correct 354 ms 4332 KB Output is correct
17 Correct 517 ms 5228 KB Output is correct
18 Correct 481 ms 4716 KB Output is correct
19 Correct 970 ms 12004 KB Output is correct
20 Correct 1578 ms 5376 KB Output is correct
21 Correct 271 ms 2796 KB Output is correct
22 Correct 1743 ms 7192 KB Output is correct
23 Correct 689 ms 10264 KB Output is correct
24 Correct 728 ms 7192 KB Output is correct
25 Correct 1372 ms 10392 KB Output is correct
26 Correct 1049 ms 10648 KB Output is correct
27 Correct 980 ms 10052 KB Output is correct
28 Correct 735 ms 52368 KB Output is correct
29 Correct 1522 ms 55280 KB Output is correct
30 Correct 2531 ms 36460 KB Output is correct
31 Correct 2329 ms 30112 KB Output is correct
32 Correct 376 ms 2668 KB Output is correct
33 Correct 519 ms 3480 KB Output is correct
34 Correct 999 ms 52400 KB Output is correct
35 Correct 1102 ms 28960 KB Output is correct
36 Correct 2065 ms 52700 KB Output is correct
37 Correct 1691 ms 51972 KB Output is correct
38 Correct 1686 ms 51188 KB Output is correct
39 Correct 1062 ms 115648 KB Output is correct
40 Correct 2551 ms 117580 KB Output is correct
41 Correct 3708 ms 78664 KB Output is correct
42 Correct 3423 ms 59788 KB Output is correct
43 Correct 1543 ms 112440 KB Output is correct
44 Correct 480 ms 10984 KB Output is correct
45 Correct 1381 ms 60176 KB Output is correct
46 Correct 2868 ms 116644 KB Output is correct
47 Correct 2900 ms 116556 KB Output is correct
48 Correct 2751 ms 116280 KB Output is correct
49 Correct 1 ms 364 KB Output is correct