oj.uz

Submission #375739

# Submission time Handle Problem Language Result Execution time Memory
375739 2021-03-09T22:46:27 Z vot808 Game (IOI13_game) C++17
80 / 100
 4164 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 = 405447;

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]) {
				// 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);
	// cout << tree.tree.size() << endl;
}
 
ll calculate(int P, int Q, int U, int V) {
	// cout << tree.tree.size() << endl;
	return tree.query(P, U, Q, V, 0, MXR, 0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 47980 KB Output is correct
2 Correct 57 ms 47980 KB Output is correct
3 Correct 57 ms 47980 KB Output is correct
4 Correct 56 ms 47980 KB Output is correct
5 Correct 58 ms 47980 KB Output is correct
6 Correct 57 ms 47980 KB Output is correct
7 Correct 56 ms 47980 KB Output is correct
8 Correct 56 ms 47980 KB Output is correct
9 Correct 56 ms 47980 KB Output is correct
10 Correct 56 ms 48128 KB Output is correct
11 Correct 65 ms 47996 KB Output is correct
12 Correct 56 ms 47980 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 47852 KB Output is correct
2 Correct 57 ms 47864 KB Output is correct
3 Correct 58 ms 47980 KB Output is correct
4 Correct 607 ms 58072 KB Output is correct
5 Correct 495 ms 58456 KB Output is correct
6 Correct 547 ms 54956 KB Output is correct
7 Correct 587 ms 54368 KB Output is correct
8 Correct 431 ms 52960 KB Output is correct
9 Correct 581 ms 54500 KB Output is correct
10 Correct 536 ms 54452 KB Output is correct
11 Correct 56 ms 47892 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 47980 KB Output is correct
2 Correct 62 ms 48108 KB Output is correct
3 Correct 59 ms 47980 KB Output is correct
4 Correct 56 ms 47980 KB Output is correct
5 Correct 57 ms 47980 KB Output is correct
6 Correct 57 ms 47980 KB Output is correct
7 Correct 56 ms 47980 KB Output is correct
8 Correct 57 ms 47980 KB Output is correct
9 Correct 56 ms 48108 KB Output is correct
10 Correct 57 ms 48000 KB Output is correct
11 Correct 64 ms 47980 KB Output is correct
12 Correct 1031 ms 60516 KB Output is correct
13 Correct 1621 ms 52276 KB Output is correct
14 Correct 357 ms 48620 KB Output is correct
15 Correct 1859 ms 53996 KB Output is correct
16 Correct 706 ms 61036 KB Output is correct
17 Correct 880 ms 56272 KB Output is correct
18 Correct 1386 ms 61356 KB Output is correct
19 Correct 1244 ms 61664 KB Output is correct
20 Correct 1201 ms 60908 KB Output is correct
21 Correct 71 ms 47980 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 48108 KB Output is correct
2 Correct 60 ms 48048 KB Output is correct
3 Correct 57 ms 47980 KB Output is correct
4 Correct 56 ms 47980 KB Output is correct
5 Correct 56 ms 47980 KB Output is correct
6 Correct 57 ms 47980 KB Output is correct
7 Correct 57 ms 47980 KB Output is correct
8 Correct 57 ms 47980 KB Output is correct
9 Correct 56 ms 47980 KB Output is correct
10 Correct 57 ms 47980 KB Output is correct
11 Correct 74 ms 47980 KB Output is correct
12 Correct 610 ms 57920 KB Output is correct
13 Correct 491 ms 58452 KB Output is correct
14 Correct 555 ms 54684 KB Output is correct
15 Correct 623 ms 54508 KB Output is correct
16 Correct 519 ms 53088 KB Output is correct
17 Correct 589 ms 54688 KB Output is correct
18 Correct 557 ms 54228 KB Output is correct
19 Correct 1051 ms 60492 KB Output is correct
20 Correct 1603 ms 52204 KB Output is correct
21 Correct 348 ms 48620 KB Output is correct
22 Correct 1852 ms 54128 KB Output is correct
23 Correct 703 ms 60908 KB Output is correct
24 Correct 870 ms 56116 KB Output is correct
25 Correct 1407 ms 61536 KB Output is correct
26 Correct 1258 ms 61504 KB Output is correct
27 Correct 1163 ms 60880 KB Output is correct
28 Correct 1211 ms 181616 KB Output is correct
29 Correct 2167 ms 197352 KB Output is correct
30 Correct 4112 ms 158500 KB Output is correct
31 Correct 3951 ms 137132 KB Output is correct
32 Correct 605 ms 48876 KB Output is correct
33 Correct 822 ms 51180 KB Output is correct
34 Correct 1486 ms 194548 KB Output is correct
35 Correct 1615 ms 122532 KB Output is correct
36 Correct 3010 ms 194964 KB Output is correct
37 Correct 2565 ms 194972 KB Output is correct
38 Correct 2584 ms 194264 KB Output is correct
39 Correct 2123 ms 161300 KB Output is correct
40 Correct 58 ms 47980 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 47928 KB Output is correct
2 Correct 56 ms 47980 KB Output is correct
3 Correct 57 ms 47980 KB Output is correct
4 Correct 61 ms 47932 KB Output is correct
5 Correct 56 ms 47980 KB Output is correct
6 Correct 60 ms 47980 KB Output is correct
7 Correct 56 ms 47980 KB Output is correct
8 Correct 62 ms 47980 KB Output is correct
9 Correct 57 ms 48108 KB Output is correct
10 Correct 57 ms 47980 KB Output is correct
11 Correct 64 ms 47980 KB Output is correct
12 Correct 611 ms 57944 KB Output is correct
13 Correct 480 ms 58196 KB Output is correct
14 Correct 553 ms 55000 KB Output is correct
15 Correct 593 ms 54512 KB Output is correct
16 Correct 439 ms 53232 KB Output is correct
17 Correct 593 ms 54680 KB Output is correct
18 Correct 533 ms 54356 KB Output is correct
19 Correct 1027 ms 60432 KB Output is correct
20 Correct 1627 ms 52348 KB Output is correct
21 Correct 351 ms 48716 KB Output is correct
22 Correct 1852 ms 54048 KB Output is correct
23 Correct 712 ms 61036 KB Output is correct
24 Correct 886 ms 56196 KB Output is correct
25 Correct 1398 ms 61520 KB Output is correct
26 Correct 1270 ms 61388 KB Output is correct
27 Correct 1192 ms 61048 KB Output is correct
28 Correct 1214 ms 181548 KB Output is correct
29 Correct 2238 ms 197388 KB Output is correct
30 Correct 4164 ms 158480 KB Output is correct
31 Correct 3966 ms 137320 KB Output is correct
32 Correct 605 ms 49132 KB Output is correct
33 Correct 806 ms 51052 KB Output is correct
34 Correct 1487 ms 194508 KB Output is correct
35 Correct 1569 ms 122556 KB Output is correct
36 Correct 3085 ms 194600 KB Output is correct
37 Correct 2620 ms 195036 KB Output is correct
38 Correct 2480 ms 194460 KB Output is correct
39 Runtime error 1362 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -