oj.uz

Submission #375737

# Submission time Handle Problem Language Result Execution time Memory
375737 2021-03-09T22:34:19 Z vot808 Game (IOI13_game) C++17
80 / 100
 4157 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 = 300000;
 
struct SegmentTree {
	public:
	vector<ii> c;
	vector<ll> tree;
	int pt = 1;
	
	void update(int &i, ll &val, int l, int r, int p, ii &xc, ii &corresp, SegmentTree xtree[]) {
		if (l == r) {
			if (!xc[0] and !xc[1]) tree[p] = val;
			else {
				tree[p] = __gcd((xc[0] and corresp[0]) ? xtree[xc[0]].tree[corresp[0]] : 0, (xc[1] and corresp[1]) ? xtree[xc[1]].tree[corresp[1]] : 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 (xc[0] and (corresp[0] or p == 0)) corresp[0] = xtree[xc[0]].c[corresp[0]][s];
		if (xc[1] and (corresp[1] or p == 0)) corresp[1] = xtree[xc[1]].c[corresp[1]][s];
		
		update(i, val, s ? mid+1 : l, s ? r : mid, c[p][s], xc, corresp, 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:
	ii c[MXL];
	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]);
		}
		
		ii temp = {0, 0};
		tree[p].update(j, val, 0, MXC, 0, c[p], temp, 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);
	// }
};
 
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 41 ms 35564 KB Output is correct
2 Correct 43 ms 35564 KB Output is correct
3 Correct 49 ms 35564 KB Output is correct
4 Correct 41 ms 35564 KB Output is correct
5 Correct 42 ms 35692 KB Output is correct
6 Correct 43 ms 35564 KB Output is correct
7 Correct 43 ms 35564 KB Output is correct
8 Correct 42 ms 35564 KB Output is correct
9 Correct 48 ms 35676 KB Output is correct
10 Correct 42 ms 35564 KB Output is correct
11 Correct 43 ms 35564 KB Output is correct
12 Correct 42 ms 35564 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 35564 KB Output is correct
2 Correct 42 ms 35564 KB Output is correct
3 Correct 51 ms 35508 KB Output is correct
4 Correct 599 ms 45396 KB Output is correct
5 Correct 481 ms 45896 KB Output is correct
6 Correct 612 ms 42336 KB Output is correct
7 Correct 576 ms 42140 KB Output is correct
8 Correct 439 ms 40544 KB Output is correct
9 Correct 588 ms 42204 KB Output is correct
10 Correct 557 ms 41940 KB Output is correct
11 Correct 42 ms 35564 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 35564 KB Output is correct
2 Correct 43 ms 35564 KB Output is correct
3 Correct 50 ms 35692 KB Output is correct
4 Correct 46 ms 35564 KB Output is correct
5 Correct 51 ms 35564 KB Output is correct
6 Correct 43 ms 35564 KB Output is correct
7 Correct 42 ms 35564 KB Output is correct
8 Correct 51 ms 35564 KB Output is correct
9 Correct 49 ms 35564 KB Output is correct
10 Correct 44 ms 35564 KB Output is correct
11 Correct 42 ms 35584 KB Output is correct
12 Correct 1026 ms 48108 KB Output is correct
13 Correct 1618 ms 40076 KB Output is correct
14 Correct 338 ms 36204 KB Output is correct
15 Correct 1879 ms 41600 KB Output is correct
16 Correct 717 ms 48584 KB Output is correct
17 Correct 939 ms 43824 KB Output is correct
18 Correct 1440 ms 49132 KB Output is correct
19 Correct 1255 ms 49260 KB Output is correct
20 Correct 1207 ms 48616 KB Output is correct
21 Correct 47 ms 35564 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 35692 KB Output is correct
2 Correct 43 ms 35564 KB Output is correct
3 Correct 48 ms 35564 KB Output is correct
4 Correct 42 ms 35564 KB Output is correct
5 Correct 42 ms 35564 KB Output is correct
6 Correct 48 ms 35692 KB Output is correct
7 Correct 45 ms 35564 KB Output is correct
8 Correct 47 ms 35564 KB Output is correct
9 Correct 49 ms 35564 KB Output is correct
10 Correct 42 ms 35564 KB Output is correct
11 Correct 44 ms 35564 KB Output is correct
12 Correct 601 ms 45500 KB Output is correct
13 Correct 467 ms 45780 KB Output is correct
14 Correct 552 ms 42340 KB Output is correct
15 Correct 609 ms 42076 KB Output is correct
16 Correct 421 ms 40800 KB Output is correct
17 Correct 558 ms 42332 KB Output is correct
18 Correct 561 ms 42332 KB Output is correct
19 Correct 1050 ms 48116 KB Output is correct
20 Correct 1647 ms 40048 KB Output is correct
21 Correct 339 ms 36204 KB Output is correct
22 Correct 1862 ms 41608 KB Output is correct
23 Correct 694 ms 48480 KB Output is correct
24 Correct 894 ms 43832 KB Output is correct
25 Correct 1507 ms 49068 KB Output is correct
26 Correct 1309 ms 49388 KB Output is correct
27 Correct 1197 ms 48360 KB Output is correct
28 Correct 1268 ms 169420 KB Output is correct
29 Correct 2208 ms 184732 KB Output is correct
30 Correct 4157 ms 146076 KB Output is correct
31 Correct 3963 ms 124604 KB Output is correct
32 Correct 577 ms 36460 KB Output is correct
33 Correct 794 ms 38764 KB Output is correct
34 Correct 1480 ms 182300 KB Output is correct
35 Correct 1699 ms 110140 KB Output is correct
36 Correct 3023 ms 182164 KB Output is correct
37 Correct 2572 ms 182388 KB Output is correct
38 Correct 2549 ms 182040 KB Output is correct
39 Correct 2170 ms 148900 KB Output is correct
40 Correct 41 ms 35564 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 35712 KB Output is correct
2 Correct 44 ms 35692 KB Output is correct
3 Correct 48 ms 35692 KB Output is correct
4 Correct 41 ms 35564 KB Output is correct
5 Correct 42 ms 35564 KB Output is correct
6 Correct 45 ms 35692 KB Output is correct
7 Correct 42 ms 35564 KB Output is correct
8 Correct 42 ms 35564 KB Output is correct
9 Correct 48 ms 35564 KB Output is correct
10 Correct 42 ms 35564 KB Output is correct
11 Correct 42 ms 35564 KB Output is correct
12 Correct 597 ms 45472 KB Output is correct
13 Correct 483 ms 45748 KB Output is correct
14 Correct 568 ms 42352 KB Output is correct
15 Correct 615 ms 42068 KB Output is correct
16 Correct 423 ms 40672 KB Output is correct
17 Correct 584 ms 42204 KB Output is correct
18 Correct 532 ms 41812 KB Output is correct
19 Correct 1022 ms 48116 KB Output is correct
20 Correct 1643 ms 39832 KB Output is correct
21 Correct 333 ms 36204 KB Output is correct
22 Correct 1835 ms 41652 KB Output is correct
23 Correct 729 ms 48620 KB Output is correct
24 Correct 853 ms 43884 KB Output is correct
25 Correct 1403 ms 49004 KB Output is correct
26 Correct 1210 ms 49128 KB Output is correct
27 Correct 1204 ms 48568 KB Output is correct
28 Correct 1205 ms 169260 KB Output is correct
29 Correct 2262 ms 184956 KB Output is correct
30 Correct 4104 ms 146096 KB Output is correct
31 Correct 3919 ms 124640 KB Output is correct
32 Correct 592 ms 36564 KB Output is correct
33 Correct 834 ms 38836 KB Output is correct
34 Correct 1470 ms 182116 KB Output is correct
35 Correct 1651 ms 110012 KB Output is correct
36 Correct 3014 ms 182268 KB Output is correct
37 Correct 2509 ms 182524 KB Output is correct
38 Correct 2578 ms 181940 KB Output is correct
39 Runtime error 1462 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -