oj.uz

Submission #375734

# Submission time Handle Problem Language Result Execution time Memory
375734 2021-03-09T22:30:40 Z vot808 Game (IOI13_game) C++17
63 / 100
 1917 ms 71032 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 = 40000;
 
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 8 ms 4972 KB Output is correct
2 Correct 7 ms 5100 KB Output is correct
3 Correct 7 ms 5100 KB Output is correct
4 Correct 6 ms 4972 KB Output is correct
5 Correct 6 ms 4972 KB Output is correct
6 Correct 6 ms 5100 KB Output is correct
7 Correct 6 ms 4972 KB Output is correct
8 Correct 6 ms 4972 KB Output is correct
9 Correct 6 ms 5100 KB Output is correct
10 Correct 7 ms 5100 KB Output is correct
11 Correct 7 ms 5100 KB Output is correct
12 Correct 6 ms 4972 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5100 KB Output is correct
2 Correct 6 ms 4972 KB Output is correct
3 Correct 6 ms 4972 KB Output is correct
4 Correct 555 ms 15064 KB Output is correct
5 Correct 466 ms 15452 KB Output is correct
6 Correct 514 ms 11960 KB Output is correct
7 Correct 551 ms 11616 KB Output is correct
8 Correct 371 ms 10024 KB Output is correct
9 Correct 607 ms 11868 KB Output is correct
10 Correct 511 ms 11500 KB Output is correct
11 Correct 6 ms 4972 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4972 KB Output is correct
2 Correct 7 ms 5100 KB Output is correct
3 Correct 9 ms 5100 KB Output is correct
4 Correct 7 ms 5100 KB Output is correct
5 Correct 6 ms 4972 KB Output is correct
6 Correct 7 ms 5100 KB Output is correct
7 Correct 6 ms 4972 KB Output is correct
8 Correct 6 ms 4972 KB Output is correct
9 Correct 7 ms 5100 KB Output is correct
10 Correct 7 ms 5100 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 1018 ms 17676 KB Output is correct
13 Correct 1586 ms 9644 KB Output is correct
14 Correct 310 ms 5612 KB Output is correct
15 Correct 1804 ms 11012 KB Output is correct
16 Correct 649 ms 18052 KB Output is correct
17 Correct 829 ms 13348 KB Output is correct
18 Correct 1443 ms 18576 KB Output is correct
19 Correct 1261 ms 18592 KB Output is correct
20 Correct 1172 ms 18028 KB Output is correct
21 Correct 6 ms 4972 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4972 KB Output is correct
2 Correct 7 ms 5100 KB Output is correct
3 Correct 7 ms 5228 KB Output is correct
4 Correct 6 ms 4972 KB Output is correct
5 Correct 9 ms 4972 KB Output is correct
6 Correct 7 ms 5100 KB Output is correct
7 Correct 6 ms 4972 KB Output is correct
8 Correct 6 ms 4972 KB Output is correct
9 Correct 7 ms 5100 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 7 ms 5100 KB Output is correct
12 Correct 554 ms 14936 KB Output is correct
13 Correct 442 ms 15316 KB Output is correct
14 Correct 523 ms 11820 KB Output is correct
15 Correct 626 ms 11744 KB Output is correct
16 Correct 398 ms 10080 KB Output is correct
17 Correct 537 ms 11760 KB Output is correct
18 Correct 501 ms 11476 KB Output is correct
19 Correct 1016 ms 17492 KB Output is correct
20 Correct 1564 ms 9432 KB Output is correct
21 Correct 306 ms 5740 KB Output is correct
22 Correct 1876 ms 10952 KB Output is correct
23 Correct 667 ms 17900 KB Output is correct
24 Correct 902 ms 13296 KB Output is correct
25 Correct 1415 ms 18592 KB Output is correct
26 Correct 1293 ms 18668 KB Output is correct
27 Correct 1131 ms 17900 KB Output is correct
28 Runtime error 230 ms 71032 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 4972 KB Output is correct
2 Correct 7 ms 5228 KB Output is correct
3 Correct 7 ms 5100 KB Output is correct
4 Correct 7 ms 4972 KB Output is correct
5 Correct 6 ms 4972 KB Output is correct
6 Correct 7 ms 5100 KB Output is correct
7 Correct 6 ms 4972 KB Output is correct
8 Correct 6 ms 4972 KB Output is correct
9 Correct 7 ms 5100 KB Output is correct
10 Correct 6 ms 5100 KB Output is correct
11 Correct 7 ms 5100 KB Output is correct
12 Correct 552 ms 15072 KB Output is correct
13 Correct 420 ms 15316 KB Output is correct
14 Correct 528 ms 11900 KB Output is correct
15 Correct 571 ms 11660 KB Output is correct
16 Correct 380 ms 10244 KB Output is correct
17 Correct 557 ms 11740 KB Output is correct
18 Correct 503 ms 11476 KB Output is correct
19 Correct 955 ms 17632 KB Output is correct
20 Correct 1583 ms 9324 KB Output is correct
21 Correct 300 ms 5868 KB Output is correct
22 Correct 1917 ms 10944 KB Output is correct
23 Correct 669 ms 18044 KB Output is correct
24 Correct 840 ms 13352 KB Output is correct
25 Correct 1402 ms 18552 KB Output is correct
26 Correct 1263 ms 18588 KB Output is correct
27 Correct 1162 ms 18072 KB Output is correct
28 Runtime error 242 ms 70852 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -