oj.uz

Submission #375722

# Submission time Handle Problem Language Result Execution time Memory
375722 2021-03-09T21:14:23 Z vot808 Game (IOI13_game) C++17
80 / 100
 4051 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 {
				ll v1 = (xc[0] and corresp[0]) ? xtree[xc[0]].tree[corresp[0]] : 0, v2 = (xc[1] and corresp[1]) ? xtree[xc[1]].tree[corresp[1]] : 0;
				tree[p] = __gcd(v1, v2);
			}
			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];
		
		// cout << i << " " << l << " " << r << endl;
		// cout << xc[0] << " " << xc[1] << " " << corresp[0] << " " << corresp[1] << endl; 
		// assert(!((!!xc[0]) ^ (!!corresp[0])));
		// assert(!((!!xc[1]) ^ (!!corresp[1])));
		
		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]);
		}
		
		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); 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); 
	// return g;
}

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 0 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 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 380 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 534 ms 10836 KB Output is correct
5 Correct 462 ms 14676 KB Output is correct
6 Correct 489 ms 11616 KB Output is correct
7 Correct 572 ms 11484 KB Output is correct
8 Correct 383 ms 9640 KB Output is correct
9 Correct 596 ms 11788 KB Output is correct
10 Correct 503 ms 11476 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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 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 962 ms 13636 KB Output is correct
13 Correct 1535 ms 8812 KB Output is correct
14 Correct 309 ms 5868 KB Output is correct
15 Correct 1723 ms 10988 KB Output is correct
16 Correct 669 ms 18028 KB Output is correct
17 Correct 895 ms 13804 KB Output is correct
18 Correct 1377 ms 19564 KB Output is correct
19 Correct 1220 ms 19904 KB Output is correct
20 Correct 1081 ms 19180 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 2 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 561 ms 10908 KB Output is correct
13 Correct 408 ms 14420 KB Output is correct
14 Correct 493 ms 11616 KB Output is correct
15 Correct 564 ms 11356 KB Output is correct
16 Correct 383 ms 9704 KB Output is correct
17 Correct 528 ms 11612 KB Output is correct
18 Correct 489 ms 11348 KB Output is correct
19 Correct 949 ms 17260 KB Output is correct
20 Correct 1502 ms 8812 KB Output is correct
21 Correct 332 ms 5740 KB Output is correct
22 Correct 1713 ms 11244 KB Output is correct
23 Correct 644 ms 17900 KB Output is correct
24 Correct 850 ms 13824 KB Output is correct
25 Correct 1419 ms 19732 KB Output is correct
26 Correct 1206 ms 19664 KB Output is correct
27 Correct 1125 ms 19144 KB Output is correct
28 Correct 1228 ms 165024 KB Output is correct
29 Correct 2202 ms 180256 KB Output is correct
30 Correct 4051 ms 129572 KB Output is correct
31 Correct 3845 ms 105832 KB Output is correct
32 Correct 559 ms 10476 KB Output is correct
33 Correct 761 ms 12944 KB Output is correct
34 Correct 1464 ms 174500 KB Output is correct
35 Correct 1607 ms 95280 KB Output is correct
36 Correct 2971 ms 177848 KB Output is correct
37 Correct 2599 ms 178116 KB Output is correct
38 Correct 2560 ms 177796 KB Output is correct
39 Correct 2100 ms 141780 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 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 0 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 526 ms 10972 KB Output is correct
13 Correct 419 ms 14676 KB Output is correct
14 Correct 519 ms 11748 KB Output is correct
15 Correct 596 ms 11472 KB Output is correct
16 Correct 376 ms 9736 KB Output is correct
17 Correct 536 ms 11716 KB Output is correct
18 Correct 491 ms 11348 KB Output is correct
19 Correct 1020 ms 17332 KB Output is correct
20 Correct 1543 ms 8928 KB Output is correct
21 Correct 308 ms 5740 KB Output is correct
22 Correct 1811 ms 11084 KB Output is correct
23 Correct 656 ms 18056 KB Output is correct
24 Correct 827 ms 14060 KB Output is correct
25 Correct 1372 ms 19572 KB Output is correct
26 Correct 1201 ms 19576 KB Output is correct
27 Correct 1146 ms 19200 KB Output is correct
28 Correct 1265 ms 164980 KB Output is correct
29 Correct 2239 ms 180284 KB Output is correct
30 Correct 4027 ms 129628 KB Output is correct
31 Correct 3877 ms 105992 KB Output is correct
32 Correct 564 ms 10476 KB Output is correct
33 Correct 811 ms 13008 KB Output is correct
34 Correct 1456 ms 174364 KB Output is correct
35 Correct 1650 ms 95172 KB Output is correct
36 Correct 2983 ms 177808 KB Output is correct
37 Correct 2586 ms 178220 KB Output is correct
38 Correct 2595 ms 177768 KB Output is correct
39 Runtime error 1506 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -