oj.uz

Submission #375733

# Submission time Handle Problem Language Result Execution time Memory
375733 2021-03-09T22:28:57 Z vot808 Game (IOI13_game) C++17
63 / 100
 1726 ms 53336 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 = 30000;
 
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]);
		}
		
		tree[p].update(j, val, 0, MXC, 0, c[p], {0, 0}, 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 5 ms 3820 KB Output is correct
2 Correct 5 ms 3968 KB Output is correct
3 Correct 6 ms 3948 KB Output is correct
4 Correct 5 ms 3820 KB Output is correct
5 Correct 5 ms 3820 KB Output is correct
6 Correct 5 ms 3948 KB Output is correct
7 Correct 5 ms 3820 KB Output is correct
8 Correct 5 ms 3840 KB Output is correct
9 Correct 6 ms 3948 KB Output is correct
10 Correct 5 ms 3820 KB Output is correct
11 Correct 6 ms 3820 KB Output is correct
12 Correct 5 ms 3820 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3840 KB Output is correct
2 Correct 5 ms 3820 KB Output is correct
3 Correct 5 ms 3900 KB Output is correct
4 Correct 538 ms 13916 KB Output is correct
5 Correct 415 ms 14288 KB Output is correct
6 Correct 499 ms 10616 KB Output is correct
7 Correct 549 ms 10332 KB Output is correct
8 Correct 391 ms 9060 KB Output is correct
9 Correct 548 ms 10600 KB Output is correct
10 Correct 495 ms 10180 KB Output is correct
11 Correct 5 ms 3820 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3820 KB Output is correct
2 Correct 6 ms 3948 KB Output is correct
3 Correct 6 ms 3948 KB Output is correct
4 Correct 5 ms 3820 KB Output is correct
5 Correct 6 ms 3820 KB Output is correct
6 Correct 5 ms 3948 KB Output is correct
7 Correct 5 ms 3820 KB Output is correct
8 Correct 5 ms 3820 KB Output is correct
9 Correct 6 ms 3948 KB Output is correct
10 Correct 5 ms 3820 KB Output is correct
11 Correct 6 ms 3820 KB Output is correct
12 Correct 958 ms 16364 KB Output is correct
13 Correct 1485 ms 8116 KB Output is correct
14 Correct 300 ms 4588 KB Output is correct
15 Correct 1726 ms 10056 KB Output is correct
16 Correct 676 ms 16780 KB Output is correct
17 Correct 828 ms 12180 KB Output is correct
18 Correct 1356 ms 17132 KB Output is correct
19 Correct 1216 ms 17484 KB Output is correct
20 Correct 1091 ms 16860 KB Output is correct
21 Correct 5 ms 3820 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3820 KB Output is correct
2 Correct 5 ms 3948 KB Output is correct
3 Correct 6 ms 3948 KB Output is correct
4 Correct 5 ms 3820 KB Output is correct
5 Correct 5 ms 3820 KB Output is correct
6 Correct 7 ms 3948 KB Output is correct
7 Correct 5 ms 3820 KB Output is correct
8 Correct 5 ms 3820 KB Output is correct
9 Correct 6 ms 3948 KB Output is correct
10 Correct 5 ms 3820 KB Output is correct
11 Correct 6 ms 3820 KB Output is correct
12 Correct 538 ms 14044 KB Output is correct
13 Correct 425 ms 14164 KB Output is correct
14 Correct 495 ms 10592 KB Output is correct
15 Correct 532 ms 10552 KB Output is correct
16 Correct 368 ms 9064 KB Output is correct
17 Correct 509 ms 10588 KB Output is correct
18 Correct 473 ms 10196 KB Output is correct
19 Correct 915 ms 16492 KB Output is correct
20 Correct 1482 ms 8300 KB Output is correct
21 Correct 294 ms 4588 KB Output is correct
22 Correct 1725 ms 9680 KB Output is correct
23 Correct 647 ms 16800 KB Output is correct
24 Correct 817 ms 12140 KB Output is correct
25 Correct 1325 ms 17168 KB Output is correct
26 Correct 1164 ms 17460 KB Output is correct
27 Correct 1074 ms 16876 KB Output is correct
28 Runtime error 170 ms 53336 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3820 KB Output is correct
2 Correct 5 ms 3948 KB Output is correct
3 Correct 6 ms 3948 KB Output is correct
4 Correct 5 ms 3820 KB Output is correct
5 Correct 5 ms 3820 KB Output is correct
6 Correct 5 ms 3948 KB Output is correct
7 Correct 5 ms 3820 KB Output is correct
8 Correct 5 ms 3820 KB Output is correct
9 Correct 7 ms 3948 KB Output is correct
10 Correct 5 ms 3820 KB Output is correct
11 Correct 5 ms 3820 KB Output is correct
12 Correct 532 ms 13780 KB Output is correct
13 Correct 416 ms 14420 KB Output is correct
14 Correct 504 ms 10604 KB Output is correct
15 Correct 531 ms 10332 KB Output is correct
16 Correct 372 ms 9068 KB Output is correct
17 Correct 523 ms 10492 KB Output is correct
18 Correct 478 ms 10196 KB Output is correct
19 Correct 915 ms 16512 KB Output is correct
20 Correct 1494 ms 8264 KB Output is correct
21 Correct 296 ms 4588 KB Output is correct
22 Correct 1715 ms 9808 KB Output is correct
23 Correct 643 ms 16876 KB Output is correct
24 Correct 832 ms 12120 KB Output is correct
25 Correct 1292 ms 17388 KB Output is correct
26 Correct 1184 ms 17644 KB Output is correct
27 Correct 1074 ms 16748 KB Output is correct
28 Runtime error 167 ms 53336 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -