oj.uz

Submission #582803

# Submission time Handle Problem Language Result Execution time Memory
582803 2022-06-24T13:03:24 Z vot808 Game (IOI13_game) C++17
100 / 100
 2664 ms 42900 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 212 KB Output is correct
2 Correct 2 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 292 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 300 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 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 453 ms 11752 KB Output is correct
5 Correct 333 ms 11460 KB Output is correct
6 Correct 407 ms 8572 KB Output is correct
7 Correct 471 ms 8372 KB Output is correct
8 Correct 314 ms 7380 KB Output is correct
9 Correct 431 ms 8428 KB Output is correct
10 Correct 496 ms 8128 KB Output is correct
11 Correct 1 ms 296 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 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 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 770 ms 14292 KB Output is correct
13 Correct 1287 ms 8004 KB Output is correct
14 Correct 209 ms 5520 KB Output is correct
15 Correct 1419 ms 9508 KB Output is correct
16 Correct 569 ms 12356 KB Output is correct
17 Correct 641 ms 10340 KB Output is correct
18 Correct 1142 ms 13716 KB Output is correct
19 Correct 971 ms 13848 KB Output is correct
20 Correct 853 ms 13332 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 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 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 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 525 ms 11600 KB Output is correct
13 Correct 323 ms 11344 KB Output is correct
14 Correct 425 ms 8640 KB Output is correct
15 Correct 454 ms 8384 KB Output is correct
16 Correct 336 ms 7472 KB Output is correct
17 Correct 474 ms 8392 KB Output is correct
18 Correct 388 ms 7928 KB Output is correct
19 Correct 904 ms 14192 KB Output is correct
20 Correct 1286 ms 7952 KB Output is correct
21 Correct 240 ms 5552 KB Output is correct
22 Correct 1442 ms 9536 KB Output is correct
23 Correct 592 ms 12196 KB Output is correct
24 Correct 623 ms 10316 KB Output is correct
25 Correct 1010 ms 13720 KB Output is correct
26 Correct 855 ms 13864 KB Output is correct
27 Correct 825 ms 13336 KB Output is correct
28 Correct 380 ms 24068 KB Output is correct
29 Correct 984 ms 26924 KB Output is correct
30 Correct 1809 ms 17336 KB Output is correct
31 Correct 1747 ms 14820 KB Output is correct
32 Correct 248 ms 10028 KB Output is correct
33 Correct 333 ms 10140 KB Output is correct
34 Correct 685 ms 20868 KB Output is correct
35 Correct 766 ms 17388 KB Output is correct
36 Correct 1524 ms 24836 KB Output is correct
37 Correct 1152 ms 25072 KB Output is correct
38 Correct 1115 ms 24532 KB Output is correct
39 Correct 932 ms 21208 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 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 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 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 456 ms 11564 KB Output is correct
13 Correct 333 ms 11460 KB Output is correct
14 Correct 382 ms 8632 KB Output is correct
15 Correct 486 ms 8320 KB Output is correct
16 Correct 323 ms 7428 KB Output is correct
17 Correct 420 ms 8420 KB Output is correct
18 Correct 398 ms 7904 KB Output is correct
19 Correct 812 ms 14180 KB Output is correct
20 Correct 1301 ms 8156 KB Output is correct
21 Correct 208 ms 5576 KB Output is correct
22 Correct 1441 ms 9576 KB Output is correct
23 Correct 566 ms 12332 KB Output is correct
24 Correct 658 ms 10404 KB Output is correct
25 Correct 1161 ms 13672 KB Output is correct
26 Correct 1002 ms 13876 KB Output is correct
27 Correct 812 ms 13372 KB Output is correct
28 Correct 486 ms 24080 KB Output is correct
29 Correct 1083 ms 26752 KB Output is correct
30 Correct 1878 ms 17240 KB Output is correct
31 Correct 1713 ms 14928 KB Output is correct
32 Correct 234 ms 10076 KB Output is correct
33 Correct 347 ms 10240 KB Output is correct
34 Correct 739 ms 20716 KB Output is correct
35 Correct 782 ms 17400 KB Output is correct
36 Correct 1696 ms 24908 KB Output is correct
37 Correct 1141 ms 25032 KB Output is correct
38 Correct 1092 ms 24640 KB Output is correct
39 Correct 634 ms 40524 KB Output is correct
40 Correct 1870 ms 42900 KB Output is correct
41 Correct 2664 ms 29676 KB Output is correct
42 Correct 2378 ms 23620 KB Output is correct
43 Correct 1031 ms 37600 KB Output is correct
44 Correct 280 ms 10564 KB Output is correct
45 Correct 945 ms 20968 KB Output is correct
46 Correct 2300 ms 41772 KB Output is correct
47 Correct 2240 ms 41944 KB Output is correct
48 Correct 1975 ms 41392 KB Output is correct
49 Correct 1 ms 212 KB Output is correct