oj.uz

Submission #375991

# Submission time Handle Problem Language Result Execution time Memory
375991 2021-03-10T14:35:01 Z vot808 Game (IOI13_game) C++17
100 / 100
 3179 ms 43272 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) {
		// cout << "updating in y range " << l[p] << " " << r[p] << " at index " << i << endl;
		if (l[p] == r[p]) {
			// cout << "/// setting leaf to " << val << endl;
			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
			// Deserves a CF Blog? :P
			tree.resize(pt+1); c.resize(pt+1); l.push_back(i); r.push_back(i);
			// cout << "!! creating leaf node " << i << " " << i << " on side " << s << endl;
			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 on different sides.
			// It then reduces to the previous case for this newly create interval node.
			
			// cout << "y child exists but not correct range cuz currently is " << l[c[p][s]] << " " << r[c[p][s]] << endl;
			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;
			}
			
			// cout << "~~~ creating " << cl << " " << cr << " and attaching " << l[c[p][s]] << " " << r[c[p][s]] << " to " << (r[c[p][s]] > cmid) << endl;
			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;
		// cout << "in y range " << l[p] << " " << r[p] << " for query range " << i << " " << j << endl;
		// if (c[p][0]) cout << "\thas left child " << l[c[p][0]] << " " << r[c[p][0]] << endl;
		// if (c[p][1]) cout << "\thas right child " << l[c[p][1]] << " " << r[c[p][1]] << endl;
		
		if (l[p] >= i and r[p] <= j) {
			// cout << "y range " << l[p] << " " << r[p] << " gives " << tree[p] << endl;
			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;
	vi l, r;
	vector<SegmentTree> tree;
	int pt = 1;
	
	void update(int &i, int &j, ll val, int p) {
		// cout << "updating x range " << l[p] << " " << r[p] << endl;
		// if (c[p][0]) cout << "---------\thas left child " << l[c[p][0]] << " " << r[c[p][0]] << endl;
		// if (c[p][1]) cout << "---------\thas right child " << l[c[p][1]] << " " << r[c[p][1]] << endl;
		if (l[p] != r[p]) {
			int mid = (l[p]+r[p])/2, s = i > mid;
			// Same heuristic as above
			if (!c[p][s]) {
				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) {
				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.push_back(tree[c[p][s]]); 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, j, val, c[p][s]);
		}
		
		if (l[p] != r[p]) 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);
		
		// cout << "going to y ranges of " << l[p] << " " << r[p] << endl;
		tree[p].update(j, val, 0);
	}
	
	ll query(int &xi, int &xj, int &yi, int &yj, int p) {
		if (l[p] > xj or r[p] < xi) return 0;
		if (l[p] >= xi and r[p] <= xj) {
			// cout << "querying x range " << l[p] << " " << r[p] << endl;
			return tree[p].query(yi, yj, 0);
		}
		
		return __gcd(c[p][0] ? query(xi, xj, yi, yj, c[p][0]) : 0, c[p][1] ? query(xi, xj, yi, yj, c[p][1]) : 0);
	}
	
	void build() {
		c.resize(1); tree.resize(1); l.push_back(0); r.push_back(MXR);
	}
};
 
SegmentTree2D tree;
 
void init(int R, int C) {
	// Wait, do I even need to do something here? :)
	MXR = R, MXC = C;
	tree.build();
}
 
void update(int P, int Q, ll K) {
	// cout << "------new update" << endl;
	tree.update(P, Q, K, 0);
}
 
ll calculate(int P, int Q, int U, int V) {
	return tree.query(P, U, Q, V, 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 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 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 364 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 545 ms 11824 KB Output is correct
5 Correct 413 ms 11492 KB Output is correct
6 Correct 494 ms 8908 KB Output is correct
7 Correct 533 ms 8572 KB Output is correct
8 Correct 388 ms 7660 KB Output is correct
9 Correct 564 ms 8548 KB Output is correct
10 Correct 542 ms 8020 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 2 ms 636 KB Output is correct
3 Correct 2 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 2 ms 512 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 492 KB Output is correct
12 Correct 1056 ms 14340 KB Output is correct
13 Correct 1569 ms 8236 KB Output is correct
14 Correct 254 ms 5612 KB Output is correct
15 Correct 1760 ms 9860 KB Output is correct
16 Correct 692 ms 12440 KB Output is correct
17 Correct 741 ms 10520 KB Output is correct
18 Correct 1247 ms 13976 KB Output is correct
19 Correct 1111 ms 14152 KB Output is correct
20 Correct 1053 ms 13552 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 492 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 561 ms 11848 KB Output is correct
13 Correct 448 ms 11492 KB Output is correct
14 Correct 532 ms 8920 KB Output is correct
15 Correct 531 ms 8424 KB Output is correct
16 Correct 361 ms 7552 KB Output is correct
17 Correct 521 ms 8548 KB Output is correct
18 Correct 483 ms 8164 KB Output is correct
19 Correct 1020 ms 14412 KB Output is correct
20 Correct 1645 ms 8348 KB Output is correct
21 Correct 259 ms 5740 KB Output is correct
22 Correct 1773 ms 9752 KB Output is correct
23 Correct 701 ms 12552 KB Output is correct
24 Correct 740 ms 10648 KB Output is correct
25 Correct 1393 ms 14008 KB Output is correct
26 Correct 1107 ms 14264 KB Output is correct
27 Correct 1029 ms 13448 KB Output is correct
28 Correct 514 ms 20692 KB Output is correct
29 Correct 1380 ms 24328 KB Output is correct
30 Correct 2364 ms 17564 KB Output is correct
31 Correct 2187 ms 15192 KB Output is correct
32 Correct 277 ms 8428 KB Output is correct
33 Correct 429 ms 8428 KB Output is correct
34 Correct 874 ms 21168 KB Output is correct
35 Correct 875 ms 15152 KB Output is correct
36 Correct 1950 ms 21528 KB Output is correct
37 Correct 1430 ms 21676 KB Output is correct
38 Correct 1407 ms 21292 KB Output is correct
39 Correct 1251 ms 17988 KB Output is correct
40 Correct 1 ms 364 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 492 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 550 ms 12044 KB Output is correct
13 Correct 422 ms 11784 KB Output is correct
14 Correct 518 ms 8676 KB Output is correct
15 Correct 550 ms 8424 KB Output is correct
16 Correct 360 ms 7660 KB Output is correct
17 Correct 522 ms 8420 KB Output is correct
18 Correct 489 ms 8036 KB Output is correct
19 Correct 946 ms 14484 KB Output is correct
20 Correct 1574 ms 8416 KB Output is correct
21 Correct 250 ms 5612 KB Output is correct
22 Correct 1789 ms 9692 KB Output is correct
23 Correct 701 ms 12344 KB Output is correct
24 Correct 731 ms 10648 KB Output is correct
25 Correct 1356 ms 13960 KB Output is correct
26 Correct 1093 ms 14104 KB Output is correct
27 Correct 1035 ms 13360 KB Output is correct
28 Correct 517 ms 20684 KB Output is correct
29 Correct 1359 ms 24168 KB Output is correct
30 Correct 2309 ms 17428 KB Output is correct
31 Correct 2086 ms 15240 KB Output is correct
32 Correct 279 ms 8300 KB Output is correct
33 Correct 394 ms 8556 KB Output is correct
34 Correct 865 ms 20968 KB Output is correct
35 Correct 855 ms 15360 KB Output is correct
36 Correct 1754 ms 21576 KB Output is correct
37 Correct 1361 ms 21972 KB Output is correct
38 Correct 1329 ms 21296 KB Output is correct
39 Correct 699 ms 40744 KB Output is correct
40 Correct 2222 ms 43272 KB Output is correct
41 Correct 3179 ms 29808 KB Output is correct
42 Correct 2917 ms 24084 KB Output is correct
43 Correct 1228 ms 37664 KB Output is correct
44 Correct 326 ms 9068 KB Output is correct
45 Correct 1107 ms 21168 KB Output is correct
46 Correct 2538 ms 42312 KB Output is correct
47 Correct 2545 ms 42004 KB Output is correct
48 Correct 2479 ms 41668 KB Output is correct
49 Correct 1 ms 364 KB Output is correct