oj.uz

Submission #375732

# Submission time Handle Problem Language Result Execution time Memory
375732 2021-03-09T22:08:11 Z vot808 Game (IOI13_game) C++17
80 / 100
 4193 ms 256004 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;
const int MXL = 660000;

struct SegmentTree {
	public:
	vector<ii> c;
	vector<ll> tree;
	int pt = 1;
	
	void update(int &i, ll &val, int l, int r, int p, int &xc0, int &xc1, int &corresp0, int &corresp1, SegmentTree xtree[]) {
		if (l == r) {
			if (!xc0 and !xc1) tree[p] = val;
			else {
				tree[p] = __gcd((xc0 and corresp0) ? xtree[xc0].tree[corresp0] : 0, (xc1 and corresp1) ? xtree[xc1].tree[corresp1] : 0);
			}
			return;
		}
		
		int mid = (l+r)/2, s = i > mid;
		if (!c[p][s]) {
			tree.resize(pt+1); c.resize(pt+1);
			c[p][s] = pt++;
		}
		
		if (xc0 and (corresp0 or p == 0)) corresp0 = xtree[xc0].c[corresp0][s];
		if (xc1 and (corresp1 or p == 0)) corresp1 = xtree[xc1].c[corresp1][s];
		
		update(i, val, s ? mid+1 : l, s ? r : mid, c[p][s], xc0, xc1, corresp0, corresp1, xtree);
		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 l, int r, int p) {
		if (l > j or r < i) return 0;
		if (l >= i and r <= j) return tree[p];
		
		int mid = (l+r)/2;
		return __gcd(c[p][0] ? query(i, j, l, mid, c[p][0]) : 0, c[p][1] ? query(i, j, mid+1, r, c[p][1]) : 0);
	}
	
	SegmentTree() {
		c.resize(1); tree.resize(1);
	}
};

struct SegmentTree2D {
	public:
	int c[MXL][2] = {0};
	SegmentTree tree[MXL];
	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]) c[p][s] = pt++;
			
			update(i, j, val, s ? mid+1 : l, s ? r : mid, c[p][s]);
		}
		
		int ta = 0, tb = 0;
		tree[p].update(j, val, 0, MXC, 0, c[p][0], c[p][1], ta, tb, tree);
	}
	
	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, MXC, 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) {
	// cout << "yellow" << endl;
	// 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);
}

// int main() {
	// cout << "tale" << endl;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 82924 KB Output is correct
2 Correct 93 ms 83052 KB Output is correct
3 Correct 98 ms 83052 KB Output is correct
4 Correct 95 ms 83056 KB Output is correct
5 Correct 92 ms 82924 KB Output is correct
6 Correct 94 ms 83052 KB Output is correct
7 Correct 93 ms 82924 KB Output is correct
8 Correct 95 ms 82924 KB Output is correct
9 Correct 106 ms 83052 KB Output is correct
10 Correct 101 ms 83180 KB Output is correct
11 Correct 113 ms 83108 KB Output is correct
12 Correct 95 ms 82924 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 83060 KB Output is correct
2 Correct 95 ms 82924 KB Output is correct
3 Correct 96 ms 82924 KB Output is correct
4 Correct 650 ms 93000 KB Output is correct
5 Correct 521 ms 93272 KB Output is correct
6 Correct 611 ms 89688 KB Output is correct
7 Correct 706 ms 89640 KB Output is correct
8 Correct 480 ms 88032 KB Output is correct
9 Correct 640 ms 89692 KB Output is correct
10 Correct 615 ms 89428 KB Output is correct
11 Correct 98 ms 82924 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 83240 KB Output is correct
2 Correct 97 ms 83052 KB Output is correct
3 Correct 98 ms 83052 KB Output is correct
4 Correct 93 ms 82924 KB Output is correct
5 Correct 93 ms 82924 KB Output is correct
6 Correct 113 ms 83180 KB Output is correct
7 Correct 97 ms 82924 KB Output is correct
8 Correct 95 ms 82924 KB Output is correct
9 Correct 110 ms 83052 KB Output is correct
10 Correct 106 ms 83016 KB Output is correct
11 Correct 106 ms 83052 KB Output is correct
12 Correct 1051 ms 95404 KB Output is correct
13 Correct 1665 ms 87412 KB Output is correct
14 Correct 454 ms 83692 KB Output is correct
15 Correct 1862 ms 89300 KB Output is correct
16 Correct 741 ms 95980 KB Output is correct
17 Correct 937 ms 91548 KB Output is correct
18 Correct 1486 ms 96632 KB Output is correct
19 Correct 1305 ms 96516 KB Output is correct
20 Correct 1270 ms 95812 KB Output is correct
21 Correct 93 ms 82924 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 82924 KB Output is correct
2 Correct 94 ms 83052 KB Output is correct
3 Correct 111 ms 83180 KB Output is correct
4 Correct 106 ms 82924 KB Output is correct
5 Correct 95 ms 83052 KB Output is correct
6 Correct 94 ms 83052 KB Output is correct
7 Correct 98 ms 82924 KB Output is correct
8 Correct 119 ms 82924 KB Output is correct
9 Correct 97 ms 83052 KB Output is correct
10 Correct 95 ms 82948 KB Output is correct
11 Correct 106 ms 83052 KB Output is correct
12 Correct 698 ms 92996 KB Output is correct
13 Correct 564 ms 93372 KB Output is correct
14 Correct 594 ms 89688 KB Output is correct
15 Correct 678 ms 89664 KB Output is correct
16 Correct 472 ms 88036 KB Output is correct
17 Correct 648 ms 89696 KB Output is correct
18 Correct 598 ms 89428 KB Output is correct
19 Correct 1040 ms 95504 KB Output is correct
20 Correct 1623 ms 87324 KB Output is correct
21 Correct 390 ms 83832 KB Output is correct
22 Correct 1844 ms 88812 KB Output is correct
23 Correct 742 ms 95980 KB Output is correct
24 Correct 959 ms 91216 KB Output is correct
25 Correct 1510 ms 96628 KB Output is correct
26 Correct 1372 ms 96576 KB Output is correct
27 Correct 1250 ms 95764 KB Output is correct
28 Correct 1275 ms 215340 KB Output is correct
29 Correct 2286 ms 231188 KB Output is correct
30 Correct 4193 ms 192776 KB Output is correct
31 Correct 3977 ms 171368 KB Output is correct
32 Correct 640 ms 84040 KB Output is correct
33 Correct 847 ms 86252 KB Output is correct
34 Correct 1520 ms 228280 KB Output is correct
35 Correct 1638 ms 156604 KB Output is correct
36 Correct 2994 ms 228336 KB Output is correct
37 Correct 2563 ms 228620 KB Output is correct
38 Correct 2506 ms 228004 KB Output is correct
39 Correct 2116 ms 195060 KB Output is correct
40 Correct 96 ms 82924 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 83052 KB Output is correct
2 Correct 93 ms 83052 KB Output is correct
3 Correct 99 ms 83052 KB Output is correct
4 Correct 95 ms 82924 KB Output is correct
5 Correct 94 ms 82924 KB Output is correct
6 Correct 100 ms 83180 KB Output is correct
7 Correct 95 ms 82924 KB Output is correct
8 Correct 98 ms 82924 KB Output is correct
9 Correct 94 ms 83052 KB Output is correct
10 Correct 95 ms 83052 KB Output is correct
11 Correct 106 ms 83052 KB Output is correct
12 Correct 634 ms 93016 KB Output is correct
13 Correct 520 ms 93312 KB Output is correct
14 Correct 587 ms 89688 KB Output is correct
15 Correct 625 ms 89440 KB Output is correct
16 Correct 482 ms 88168 KB Output is correct
17 Correct 607 ms 89692 KB Output is correct
18 Correct 576 ms 89456 KB Output is correct
19 Correct 1022 ms 95496 KB Output is correct
20 Correct 1617 ms 87376 KB Output is correct
21 Correct 391 ms 83692 KB Output is correct
22 Correct 1864 ms 88896 KB Output is correct
23 Correct 751 ms 96108 KB Output is correct
24 Correct 918 ms 91500 KB Output is correct
25 Correct 1423 ms 96388 KB Output is correct
26 Correct 1308 ms 96492 KB Output is correct
27 Correct 1217 ms 96048 KB Output is correct
28 Correct 1253 ms 215380 KB Output is correct
29 Correct 2232 ms 231100 KB Output is correct
30 Correct 4099 ms 192988 KB Output is correct
31 Correct 3945 ms 171496 KB Output is correct
32 Correct 639 ms 83924 KB Output is correct
33 Correct 857 ms 86252 KB Output is correct
34 Correct 1517 ms 228280 KB Output is correct
35 Correct 1738 ms 156860 KB Output is correct
36 Correct 3148 ms 228380 KB Output is correct
37 Correct 2713 ms 228716 KB Output is correct
38 Correct 2684 ms 228012 KB Output is correct
39 Runtime error 1133 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -