oj.uz

Submission #375888

# Submission time Handle Problem Language Result Execution time Memory
375888 2021-03-10T07:53:51 Z vot808 Game (IOI13_game) C++17
80 / 100
 4177 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) {
		if (l == r) {
			tree[p] = val;
			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);
		update(i, val, s ? mid+1 : l, s ? r : mid, c[p][s]);
		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};
		if (l != r) val = __gcd(c[p][0] ? tree[c[p][0]].query(j, j, 0, MXC, 0) : 0, c[p][1] ? tree[c[p][1]].query(j, j, 0, MXC, 0) : 0);
		
		tree[p].update(j, val, 0, MXC, 0);
	}
	
	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 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 384 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 591 ms 14264 KB Output is correct
5 Correct 441 ms 12244 KB Output is correct
6 Correct 515 ms 8808 KB Output is correct
7 Correct 554 ms 8284 KB Output is correct
8 Correct 395 ms 7008 KB Output is correct
9 Correct 549 ms 8668 KB Output is correct
10 Correct 535 ms 8276 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 492 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 989 ms 16620 KB Output is correct
13 Correct 1610 ms 6764 KB Output is correct
14 Correct 313 ms 2540 KB Output is correct
15 Correct 1809 ms 8496 KB Output is correct
16 Correct 691 ms 15468 KB Output is correct
17 Correct 919 ms 10860 KB Output is correct
18 Correct 1506 ms 15852 KB Output is correct
19 Correct 1197 ms 16108 KB Output is correct
20 Correct 1165 ms 15212 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 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 580 ms 13932 KB Output is correct
13 Correct 444 ms 12148 KB Output is correct
14 Correct 506 ms 8548 KB Output is correct
15 Correct 582 ms 8520 KB Output is correct
16 Correct 379 ms 7008 KB Output is correct
17 Correct 530 ms 8796 KB Output is correct
18 Correct 502 ms 8372 KB Output is correct
19 Correct 1006 ms 14828 KB Output is correct
20 Correct 1596 ms 6508 KB Output is correct
21 Correct 318 ms 2564 KB Output is correct
22 Correct 1801 ms 8416 KB Output is correct
23 Correct 713 ms 15512 KB Output is correct
24 Correct 856 ms 10732 KB Output is correct
25 Correct 1396 ms 15856 KB Output is correct
26 Correct 1268 ms 15984 KB Output is correct
27 Correct 1142 ms 15392 KB Output is correct
28 Correct 1230 ms 155932 KB Output is correct
29 Correct 2277 ms 171508 KB Output is correct
30 Correct 4138 ms 124160 KB Output is correct
31 Correct 3980 ms 100568 KB Output is correct
32 Correct 555 ms 2796 KB Output is correct
33 Correct 768 ms 5356 KB Output is correct
34 Correct 1551 ms 169248 KB Output is correct
35 Correct 1640 ms 86888 KB Output is correct
36 Correct 2949 ms 168768 KB Output is correct
37 Correct 2670 ms 168988 KB Output is correct
38 Correct 2582 ms 168588 KB Output is correct
39 Correct 2190 ms 133168 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 2 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 602 ms 14044 KB Output is correct
13 Correct 443 ms 12384 KB Output is correct
14 Correct 576 ms 8680 KB Output is correct
15 Correct 550 ms 8412 KB Output is correct
16 Correct 391 ms 7008 KB Output is correct
17 Correct 561 ms 8740 KB Output is correct
18 Correct 523 ms 8284 KB Output is correct
19 Correct 1010 ms 14708 KB Output is correct
20 Correct 1603 ms 6560 KB Output is correct
21 Correct 299 ms 2540 KB Output is correct
22 Correct 1810 ms 8364 KB Output is correct
23 Correct 688 ms 15496 KB Output is correct
24 Correct 847 ms 10604 KB Output is correct
25 Correct 1369 ms 15764 KB Output is correct
26 Correct 1197 ms 15856 KB Output is correct
27 Correct 1141 ms 15292 KB Output is correct
28 Correct 1270 ms 155940 KB Output is correct
29 Correct 2391 ms 171752 KB Output is correct
30 Correct 4177 ms 124028 KB Output is correct
31 Correct 4108 ms 100340 KB Output is correct
32 Correct 584 ms 2764 KB Output is correct
33 Correct 779 ms 5356 KB Output is correct
34 Correct 1516 ms 169380 KB Output is correct
35 Correct 1600 ms 86864 KB Output is correct
36 Correct 2917 ms 168476 KB Output is correct
37 Correct 3149 ms 168832 KB Output is correct
38 Correct 2820 ms 168520 KB Output is correct
39 Runtime error 1508 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -