oj.uz

Submission #375736

# Submission time Handle Problem Language Result Execution time Memory
375736 2021-03-09T22:32:44 Z vot808 Game (IOI13_game) C++17
63 / 100
 1808 ms 107204 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 = 60000;
 
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 9 ms 7404 KB Output is correct
2 Correct 10 ms 7404 KB Output is correct
3 Correct 10 ms 7404 KB Output is correct
4 Correct 9 ms 7404 KB Output is correct
5 Correct 9 ms 7404 KB Output is correct
6 Correct 9 ms 7404 KB Output is correct
7 Correct 9 ms 7404 KB Output is correct
8 Correct 9 ms 7404 KB Output is correct
9 Correct 11 ms 7404 KB Output is correct
10 Correct 9 ms 7532 KB Output is correct
11 Correct 10 ms 7404 KB Output is correct
12 Correct 9 ms 7404 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7404 KB Output is correct
2 Correct 9 ms 7404 KB Output is correct
3 Correct 9 ms 7404 KB Output is correct
4 Correct 572 ms 17376 KB Output is correct
5 Correct 436 ms 17620 KB Output is correct
6 Correct 500 ms 13920 KB Output is correct
7 Correct 589 ms 13928 KB Output is correct
8 Correct 378 ms 12384 KB Output is correct
9 Correct 558 ms 14052 KB Output is correct
10 Correct 527 ms 13652 KB Output is correct
11 Correct 9 ms 7404 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7404 KB Output is correct
2 Correct 10 ms 7552 KB Output is correct
3 Correct 10 ms 7404 KB Output is correct
4 Correct 9 ms 7404 KB Output is correct
5 Correct 9 ms 7404 KB Output is correct
6 Correct 10 ms 7404 KB Output is correct
7 Correct 10 ms 7404 KB Output is correct
8 Correct 9 ms 7404 KB Output is correct
9 Correct 12 ms 7404 KB Output is correct
10 Correct 9 ms 7404 KB Output is correct
11 Correct 10 ms 7404 KB Output is correct
12 Correct 970 ms 20076 KB Output is correct
13 Correct 1575 ms 11904 KB Output is correct
14 Correct 303 ms 8108 KB Output is correct
15 Correct 1808 ms 13444 KB Output is correct
16 Correct 672 ms 20400 KB Output is correct
17 Correct 826 ms 15724 KB Output is correct
18 Correct 1381 ms 21228 KB Output is correct
19 Correct 1231 ms 21228 KB Output is correct
20 Correct 1132 ms 20256 KB Output is correct
21 Correct 9 ms 7404 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7404 KB Output is correct
2 Correct 10 ms 7404 KB Output is correct
3 Correct 12 ms 7404 KB Output is correct
4 Correct 9 ms 7404 KB Output is correct
5 Correct 9 ms 7404 KB Output is correct
6 Correct 10 ms 7404 KB Output is correct
7 Correct 10 ms 7404 KB Output is correct
8 Correct 9 ms 7404 KB Output is correct
9 Correct 11 ms 7404 KB Output is correct
10 Correct 9 ms 7404 KB Output is correct
11 Correct 10 ms 7404 KB Output is correct
12 Correct 566 ms 17496 KB Output is correct
13 Correct 432 ms 17804 KB Output is correct
14 Correct 493 ms 13920 KB Output is correct
15 Correct 538 ms 13916 KB Output is correct
16 Correct 380 ms 12520 KB Output is correct
17 Correct 527 ms 14172 KB Output is correct
18 Correct 496 ms 13732 KB Output is correct
19 Correct 958 ms 19820 KB Output is correct
20 Correct 1555 ms 12168 KB Output is correct
21 Correct 307 ms 8164 KB Output is correct
22 Correct 1784 ms 13420 KB Output is correct
23 Correct 678 ms 20332 KB Output is correct
24 Correct 839 ms 15724 KB Output is correct
25 Correct 1375 ms 20972 KB Output is correct
26 Correct 1191 ms 20972 KB Output is correct
27 Correct 1127 ms 20204 KB Output is correct
28 Runtime error 352 ms 107076 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 9 ms 7404 KB Output is correct
2 Correct 12 ms 7404 KB Output is correct
3 Correct 9 ms 7404 KB Output is correct
4 Correct 9 ms 7404 KB Output is correct
5 Correct 9 ms 7404 KB Output is correct
6 Correct 10 ms 7532 KB Output is correct
7 Correct 9 ms 7404 KB Output is correct
8 Correct 9 ms 7404 KB Output is correct
9 Correct 11 ms 7404 KB Output is correct
10 Correct 9 ms 7404 KB Output is correct
11 Correct 11 ms 7404 KB Output is correct
12 Correct 560 ms 17376 KB Output is correct
13 Correct 458 ms 17748 KB Output is correct
14 Correct 502 ms 14092 KB Output is correct
15 Correct 578 ms 14024 KB Output is correct
16 Correct 382 ms 12512 KB Output is correct
17 Correct 527 ms 14044 KB Output is correct
18 Correct 521 ms 13752 KB Output is correct
19 Correct 963 ms 19948 KB Output is correct
20 Correct 1594 ms 11756 KB Output is correct
21 Correct 318 ms 8044 KB Output is correct
22 Correct 1795 ms 13560 KB Output is correct
23 Correct 679 ms 20332 KB Output is correct
24 Correct 835 ms 15724 KB Output is correct
25 Correct 1362 ms 20908 KB Output is correct
26 Correct 1190 ms 21108 KB Output is correct
27 Correct 1123 ms 20352 KB Output is correct
28 Runtime error 351 ms 107204 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -