oj.uz

Submission #375738

# Submission time Handle Problem Language Result Execution time Memory
375738 2021-03-09T22:38:05 Z vot808 Game (IOI13_game) C++17
80 / 100
 4098 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;
 
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, vector<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:
	vector<ii> c;
	vector<SegmentTree> tree;
	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]) {
				tree.resize(pt+1); c.resize(pt+1);
				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); tree.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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 562 ms 10196 KB Output is correct
5 Correct 414 ms 10580 KB Output is correct
6 Correct 493 ms 6880 KB Output is correct
7 Correct 545 ms 6748 KB Output is correct
8 Correct 433 ms 5436 KB Output is correct
9 Correct 544 ms 7028 KB Output is correct
10 Correct 499 ms 6848 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 975 ms 13164 KB Output is correct
13 Correct 1574 ms 5188 KB Output is correct
14 Correct 306 ms 1004 KB Output is correct
15 Correct 1788 ms 6880 KB Output is correct
16 Correct 662 ms 13932 KB Output is correct
17 Correct 809 ms 9220 KB Output is correct
18 Correct 1444 ms 14280 KB Output is correct
19 Correct 1222 ms 14540 KB Output is correct
20 Correct 1123 ms 13804 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 536 ms 10328 KB Output is correct
13 Correct 418 ms 10580 KB Output is correct
14 Correct 492 ms 7008 KB Output is correct
15 Correct 559 ms 6876 KB Output is correct
16 Correct 369 ms 5344 KB Output is correct
17 Correct 519 ms 7156 KB Output is correct
18 Correct 589 ms 6732 KB Output is correct
19 Correct 941 ms 13204 KB Output is correct
20 Correct 1511 ms 4964 KB Output is correct
21 Correct 306 ms 1004 KB Output is correct
22 Correct 1750 ms 6764 KB Output is correct
23 Correct 670 ms 14188 KB Output is correct
24 Correct 845 ms 9196 KB Output is correct
25 Correct 1434 ms 14188 KB Output is correct
26 Correct 1189 ms 14468 KB Output is correct
27 Correct 1129 ms 13684 KB Output is correct
28 Correct 1223 ms 154524 KB Output is correct
29 Correct 2185 ms 169884 KB Output is correct
30 Correct 4086 ms 122544 KB Output is correct
31 Correct 3924 ms 98828 KB Output is correct
32 Correct 541 ms 1260 KB Output is correct
33 Correct 752 ms 3692 KB Output is correct
34 Correct 1459 ms 167580 KB Output is correct
35 Correct 1646 ms 85528 KB Output is correct
36 Correct 2875 ms 167152 KB Output is correct
37 Correct 2582 ms 167372 KB Output is correct
38 Correct 2599 ms 166812 KB Output is correct
39 Correct 2112 ms 131752 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 538 ms 10452 KB Output is correct
13 Correct 422 ms 10580 KB Output is correct
14 Correct 505 ms 7008 KB Output is correct
15 Correct 590 ms 6932 KB Output is correct
16 Correct 383 ms 5344 KB Output is correct
17 Correct 521 ms 7132 KB Output is correct
18 Correct 487 ms 6764 KB Output is correct
19 Correct 945 ms 13164 KB Output is correct
20 Correct 1528 ms 4916 KB Output is correct
21 Correct 294 ms 1004 KB Output is correct
22 Correct 1763 ms 6908 KB Output is correct
23 Correct 672 ms 13716 KB Output is correct
24 Correct 816 ms 9196 KB Output is correct
25 Correct 1334 ms 14452 KB Output is correct
26 Correct 1189 ms 14536 KB Output is correct
27 Correct 1091 ms 13804 KB Output is correct
28 Correct 1209 ms 154524 KB Output is correct
29 Correct 2191 ms 170100 KB Output is correct
30 Correct 4098 ms 122736 KB Output is correct
31 Correct 3922 ms 99036 KB Output is correct
32 Correct 553 ms 1260 KB Output is correct
33 Correct 754 ms 3852 KB Output is correct
34 Correct 1464 ms 167704 KB Output is correct
35 Correct 1643 ms 85556 KB Output is correct
36 Correct 2949 ms 167328 KB Output is correct
37 Correct 2535 ms 167460 KB Output is correct
38 Correct 2509 ms 167164 KB Output is correct
39 Runtime error 1504 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -