oj.uz

Submission #375725

# Submission time Handle Problem Language Result Execution time Memory
375725 2021-03-09T21:18:11 Z vot808 Game (IOI13_game) C++17
80 / 100
 4066 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];
		
		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); 
	// 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 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 512 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 384 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 563 ms 10196 KB Output is correct
5 Correct 422 ms 10580 KB Output is correct
6 Correct 518 ms 7136 KB Output is correct
7 Correct 551 ms 6876 KB Output is correct
8 Correct 393 ms 5736 KB Output is correct
9 Correct 535 ms 7004 KB Output is correct
10 Correct 499 ms 6708 KB Output is correct
11 Correct 1 ms 512 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 2 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 952 ms 13036 KB Output is correct
13 Correct 1568 ms 5028 KB Output is correct
14 Correct 294 ms 1132 KB Output is correct
15 Correct 1764 ms 6636 KB Output is correct
16 Correct 677 ms 13932 KB Output is correct
17 Correct 863 ms 8940 KB Output is correct
18 Correct 1417 ms 14236 KB Output is correct
19 Correct 1309 ms 14324 KB Output is correct
20 Correct 1169 ms 13620 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 512 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 552 ms 10460 KB Output is correct
13 Correct 417 ms 10896 KB Output is correct
14 Correct 494 ms 6936 KB Output is correct
15 Correct 525 ms 6748 KB Output is correct
16 Correct 366 ms 5728 KB Output is correct
17 Correct 531 ms 7132 KB Output is correct
18 Correct 494 ms 6740 KB Output is correct
19 Correct 949 ms 13076 KB Output is correct
20 Correct 1536 ms 5228 KB Output is correct
21 Correct 306 ms 1004 KB Output is correct
22 Correct 1769 ms 6812 KB Output is correct
23 Correct 690 ms 13804 KB Output is correct
24 Correct 851 ms 8940 KB Output is correct
25 Correct 1416 ms 14384 KB Output is correct
26 Correct 1219 ms 14380 KB Output is correct
27 Correct 1085 ms 13808 KB Output is correct
28 Correct 1273 ms 154536 KB Output is correct
29 Correct 2177 ms 170160 KB Output is correct
30 Correct 4066 ms 122720 KB Output is correct
31 Correct 3959 ms 98988 KB Output is correct
32 Correct 539 ms 1404 KB Output is correct
33 Correct 802 ms 3668 KB Output is correct
34 Correct 1471 ms 167892 KB Output is correct
35 Correct 1651 ms 85472 KB Output is correct
36 Correct 3026 ms 167220 KB Output is correct
37 Correct 2537 ms 167484 KB Output is correct
38 Correct 2581 ms 166964 KB Output is correct
39 Correct 2115 ms 131740 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 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 544 ms 10196 KB Output is correct
13 Correct 422 ms 10720 KB Output is correct
14 Correct 484 ms 6880 KB Output is correct
15 Correct 517 ms 6748 KB Output is correct
16 Correct 376 ms 5612 KB Output is correct
17 Correct 529 ms 7132 KB Output is correct
18 Correct 504 ms 6612 KB Output is correct
19 Correct 982 ms 13164 KB Output is correct
20 Correct 1527 ms 4972 KB Output is correct
21 Correct 296 ms 972 KB Output is correct
22 Correct 1771 ms 6692 KB Output is correct
23 Correct 664 ms 13804 KB Output is correct
24 Correct 804 ms 9068 KB Output is correct
25 Correct 1398 ms 14316 KB Output is correct
26 Correct 1211 ms 14496 KB Output is correct
27 Correct 1060 ms 13812 KB Output is correct
28 Correct 1228 ms 154396 KB Output is correct
29 Correct 2259 ms 169932 KB Output is correct
30 Correct 4054 ms 122500 KB Output is correct
31 Correct 3874 ms 99032 KB Output is correct
32 Correct 557 ms 1260 KB Output is correct
33 Correct 770 ms 3948 KB Output is correct
34 Correct 1474 ms 167824 KB Output is correct
35 Correct 1553 ms 85468 KB Output is correct
36 Correct 2943 ms 167220 KB Output is correct
37 Correct 2618 ms 167528 KB Output is correct
38 Correct 2508 ms 167204 KB Output is correct
39 Runtime error 1482 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -