oj.uz

Submission #375735

# Submission time Handle Problem Language Result Execution time Memory
375735 2021-03-09T22:31:42 Z vot808 Game (IOI13_game) C++17
63 / 100
 1811 ms 88644 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 = 50000;
 
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]) 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);
	// }
};
 
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);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6124 KB Output is correct
2 Correct 7 ms 6124 KB Output is correct
3 Correct 8 ms 6252 KB Output is correct
4 Correct 550 ms 16088 KB Output is correct
5 Correct 426 ms 16724 KB Output is correct
6 Correct 507 ms 12888 KB Output is correct
7 Correct 526 ms 12896 KB Output is correct
8 Correct 378 ms 11396 KB Output is correct
9 Correct 567 ms 13148 KB Output is correct
10 Correct 510 ms 12628 KB Output is correct
11 Correct 7 ms 6124 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6124 KB Output is correct
2 Correct 8 ms 6252 KB Output is correct
3 Correct 9 ms 6252 KB Output is correct
4 Correct 8 ms 6124 KB Output is correct
5 Correct 8 ms 6124 KB Output is correct
6 Correct 8 ms 6252 KB Output is correct
7 Correct 8 ms 6252 KB Output is correct
8 Correct 10 ms 6252 KB Output is correct
9 Correct 8 ms 6252 KB Output is correct
10 Correct 9 ms 6252 KB Output is correct
11 Correct 9 ms 6252 KB Output is correct
12 Correct 994 ms 18884 KB Output is correct
13 Correct 1602 ms 10592 KB Output is correct
14 Correct 306 ms 6892 KB Output is correct
15 Correct 1790 ms 12140 KB Output is correct
16 Correct 683 ms 19308 KB Output is correct
17 Correct 851 ms 14444 KB Output is correct
18 Correct 1428 ms 19568 KB Output is correct
19 Correct 1244 ms 19748 KB Output is correct
20 Correct 1211 ms 19052 KB Output is correct
21 Correct 8 ms 6124 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6124 KB Output is correct
2 Correct 8 ms 6252 KB Output is correct
3 Correct 8 ms 6252 KB Output is correct
4 Correct 8 ms 6124 KB Output is correct
5 Correct 8 ms 6124 KB Output is correct
6 Correct 9 ms 6252 KB Output is correct
7 Correct 8 ms 6252 KB Output is correct
8 Correct 8 ms 6252 KB Output is correct
9 Correct 8 ms 6252 KB Output is correct
10 Correct 8 ms 6252 KB Output is correct
11 Correct 9 ms 6252 KB Output is correct
12 Correct 554 ms 16088 KB Output is correct
13 Correct 468 ms 16596 KB Output is correct
14 Correct 509 ms 13024 KB Output is correct
15 Correct 553 ms 12768 KB Output is correct
16 Correct 375 ms 11304 KB Output is correct
17 Correct 587 ms 12764 KB Output is correct
18 Correct 499 ms 12500 KB Output is correct
19 Correct 979 ms 18668 KB Output is correct
20 Correct 1555 ms 10476 KB Output is correct
21 Correct 323 ms 6892 KB Output is correct
22 Correct 1811 ms 12140 KB Output is correct
23 Correct 655 ms 19180 KB Output is correct
24 Correct 859 ms 14404 KB Output is correct
25 Correct 1409 ms 19820 KB Output is correct
26 Correct 1276 ms 19752 KB Output is correct
27 Correct 1119 ms 19092 KB Output is correct
28 Runtime error 291 ms 88644 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 7 ms 6124 KB Output is correct
2 Correct 8 ms 6252 KB Output is correct
3 Correct 9 ms 6252 KB Output is correct
4 Correct 8 ms 6124 KB Output is correct
5 Correct 8 ms 6124 KB Output is correct
6 Correct 8 ms 6252 KB Output is correct
7 Correct 8 ms 6252 KB Output is correct
8 Correct 7 ms 6252 KB Output is correct
9 Correct 8 ms 6252 KB Output is correct
10 Correct 8 ms 6252 KB Output is correct
11 Correct 9 ms 6252 KB Output is correct
12 Correct 570 ms 16088 KB Output is correct
13 Correct 434 ms 16548 KB Output is correct
14 Correct 506 ms 13016 KB Output is correct
15 Correct 535 ms 12768 KB Output is correct
16 Correct 387 ms 11440 KB Output is correct
17 Correct 528 ms 12900 KB Output is correct
18 Correct 497 ms 12628 KB Output is correct
19 Correct 977 ms 18668 KB Output is correct
20 Correct 1564 ms 10592 KB Output is correct
21 Correct 307 ms 6892 KB Output is correct
22 Correct 1802 ms 12344 KB Output is correct
23 Correct 650 ms 19308 KB Output is correct
24 Correct 839 ms 14572 KB Output is correct
25 Correct 1352 ms 19676 KB Output is correct
26 Correct 1245 ms 19808 KB Output is correct
27 Correct 1098 ms 19180 KB Output is correct
28 Runtime error 291 ms 88516 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -