oj.uz

Submission #375731

# Submission time Handle Problem Language Result Execution time Memory
375731 2021-03-09T22:05:23 Z vot808 Game (IOI13_game) C++17
63 / 100
 1741 ms 39384 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 = 22000;

struct SegmentTree {
	public:
	vector<ii> c;
	vector<ll> tree;
	int pt = 1;
	
	void update(int &i, ll &val, int l, int r, int p, int &xc0, int &xc1, int &corresp0, int &corresp1, SegmentTree xtree[]) {
		if (l == r) {
			if (!xc0 and !xc1) tree[p] = val;
			else {
				tree[p] = __gcd((xc0 and corresp0) ? xtree[xc0].tree[corresp0] : 0, (xc1 and corresp1) ? xtree[xc1].tree[corresp1] : 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 (xc0 and (corresp0 or p == 0)) corresp0 = xtree[xc0].c[corresp0][s];
		if (xc1 and (corresp1 or p == 0)) corresp1 = xtree[xc1].c[corresp1][s];
		
		update(i, val, s ? mid+1 : l, s ? r : mid, c[p][s], xc0, xc1, corresp0, corresp1, 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:
	int c[MXL][2] = {0};
	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]) c[p][s] = pt++;
			
			update(i, j, val, s ? mid+1 : l, s ? r : mid, c[p][s]);
		}
		
		int ta = 0, tb = 0;
		tree[p].update(j, val, 0, MXC, 0, c[p][0], c[p][1], ta, tb, 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) {
	// cout << "yellow" << endl;
	// 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);
}

// int main() {
	// cout << "tale" << endl;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3052 KB Output is correct
2 Correct 6 ms 3180 KB Output is correct
3 Correct 4 ms 3180 KB Output is correct
4 Correct 4 ms 3052 KB Output is correct
5 Correct 4 ms 3052 KB Output is correct
6 Correct 4 ms 3180 KB Output is correct
7 Correct 4 ms 3052 KB Output is correct
8 Correct 4 ms 3072 KB Output is correct
9 Correct 5 ms 3180 KB Output is correct
10 Correct 4 ms 3052 KB Output is correct
11 Correct 5 ms 3052 KB Output is correct
12 Correct 4 ms 3052 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3052 KB Output is correct
2 Correct 4 ms 3052 KB Output is correct
3 Correct 4 ms 3052 KB Output is correct
4 Correct 536 ms 13016 KB Output is correct
5 Correct 419 ms 13532 KB Output is correct
6 Correct 518 ms 9952 KB Output is correct
7 Correct 535 ms 9844 KB Output is correct
8 Correct 376 ms 8160 KB Output is correct
9 Correct 516 ms 9820 KB Output is correct
10 Correct 490 ms 9428 KB Output is correct
11 Correct 4 ms 3052 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3052 KB Output is correct
2 Correct 4 ms 3180 KB Output is correct
3 Correct 5 ms 3180 KB Output is correct
4 Correct 4 ms 3052 KB Output is correct
5 Correct 4 ms 3052 KB Output is correct
6 Correct 4 ms 3180 KB Output is correct
7 Correct 4 ms 3052 KB Output is correct
8 Correct 4 ms 3052 KB Output is correct
9 Correct 5 ms 3180 KB Output is correct
10 Correct 4 ms 3052 KB Output is correct
11 Correct 4 ms 3052 KB Output is correct
12 Correct 932 ms 15724 KB Output is correct
13 Correct 1505 ms 7532 KB Output is correct
14 Correct 294 ms 3692 KB Output is correct
15 Correct 1727 ms 8940 KB Output is correct
16 Correct 635 ms 15984 KB Output is correct
17 Correct 846 ms 11548 KB Output is correct
18 Correct 1319 ms 16620 KB Output is correct
19 Correct 1169 ms 16476 KB Output is correct
20 Correct 1071 ms 16128 KB Output is correct
21 Correct 4 ms 3052 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3180 KB Output is correct
2 Correct 5 ms 3180 KB Output is correct
3 Correct 5 ms 3180 KB Output is correct
4 Correct 4 ms 3052 KB Output is correct
5 Correct 4 ms 3052 KB Output is correct
6 Correct 4 ms 3180 KB Output is correct
7 Correct 4 ms 3052 KB Output is correct
8 Correct 4 ms 3052 KB Output is correct
9 Correct 5 ms 3180 KB Output is correct
10 Correct 4 ms 3052 KB Output is correct
11 Correct 4 ms 3052 KB Output is correct
12 Correct 533 ms 13144 KB Output is correct
13 Correct 409 ms 13396 KB Output is correct
14 Correct 510 ms 9728 KB Output is correct
15 Correct 545 ms 9860 KB Output is correct
16 Correct 372 ms 8288 KB Output is correct
17 Correct 502 ms 9720 KB Output is correct
18 Correct 513 ms 9428 KB Output is correct
19 Correct 918 ms 15656 KB Output is correct
20 Correct 1514 ms 7504 KB Output is correct
21 Correct 301 ms 3692 KB Output is correct
22 Correct 1735 ms 9064 KB Output is correct
23 Correct 645 ms 16108 KB Output is correct
24 Correct 813 ms 11372 KB Output is correct
25 Correct 1346 ms 16492 KB Output is correct
26 Correct 1170 ms 16588 KB Output is correct
27 Correct 1069 ms 15832 KB Output is correct
28 Runtime error 129 ms 39384 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3052 KB Output is correct
2 Correct 5 ms 3180 KB Output is correct
3 Correct 4 ms 3180 KB Output is correct
4 Correct 4 ms 3052 KB Output is correct
5 Correct 4 ms 3052 KB Output is correct
6 Correct 4 ms 3180 KB Output is correct
7 Correct 4 ms 3052 KB Output is correct
8 Correct 4 ms 3052 KB Output is correct
9 Correct 5 ms 3180 KB Output is correct
10 Correct 4 ms 3052 KB Output is correct
11 Correct 4 ms 3052 KB Output is correct
12 Correct 536 ms 13016 KB Output is correct
13 Correct 408 ms 13268 KB Output is correct
14 Correct 487 ms 9696 KB Output is correct
15 Correct 545 ms 9692 KB Output is correct
16 Correct 381 ms 8160 KB Output is correct
17 Correct 550 ms 9820 KB Output is correct
18 Correct 507 ms 9436 KB Output is correct
19 Correct 945 ms 15456 KB Output is correct
20 Correct 1518 ms 7492 KB Output is correct
21 Correct 302 ms 3748 KB Output is correct
22 Correct 1741 ms 9136 KB Output is correct
23 Correct 634 ms 16152 KB Output is correct
24 Correct 803 ms 11404 KB Output is correct
25 Correct 1309 ms 16492 KB Output is correct
26 Correct 1129 ms 16428 KB Output is correct
27 Correct 1118 ms 15980 KB Output is correct
28 Runtime error 122 ms 39384 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -