oj.uz

Submission #1087560

# Submission time Handle Problem Language Result Execution time Memory
1087560 2024-09-12T23:47:40 Z Noam527 Game (IOI13_game) C++17
80 / 100
 1782 ms 256000 KB 
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ldb;
const int md = (int)1e9 + 7;
const ll inf = 2e18;
const int OO = 1;
using namespace std;
 
#include "game.h"
 
/*
* note the "using T = int". this is the range of indicies we allow.
* note the static constant LIM. used for efficiency of both time and memory. practice shows that 64 or 128 are the best.
* ASSUMES COMMUTATIVITY - to fix, make `query` call the recursive version immediately (i.e no use of `big`).
*/
template<typename element>
struct segtree {
	using T = int;
	struct node {
		element val;
		int c[2];
		node(element v = element()) : c({ 0,0 }), val(v) {}
		int& operator [](int i) {
			return c[i];
		}
	};
	T L, R;
	vector<node> t;
 
	segtree() {}
	segtree(T LL, T RR) : L(LL), R(RR) {
		t.push_back(node()); // dummy
		t.push_back(node()); // root
	}
	int add_node() {
		t.push_back(node());
		return (int)t.size() - 1;
	}
	int go(int v, int dir) {
		if (!t[v][dir]) {
			int x = add_node(); // prevents bug from reallocation
			t[v][dir] = x;
		}
		return t[v][dir];
	}
	void fix(int v) {
		t[v].val = t[t[v][0]].val * t[t[v][1]].val;
	}
	void update(T pos, element val) {
		update(pos, val, 1, L, R);
	}
	void update(T pos, element val, int node, T nl, T nr) {
		if (nl == nr) {
			t[node].val = val;
			return;
		}
		T mid = (nl + nr) / 2;
		if (pos <= mid) update(pos, val, go(node, 0), nl, mid);
		else update(pos, val, go(node, 1), mid + 1, nr);
		fix(node);
	}
	// implement only if you need quick access to a single index (instead of range)
	element get(T i) {
		int node = 1;
		T l = L, r = R;
		while (l < r) {
			T mid = (l + r) / 2;
			if (i <= mid) {
				if (!t[node][0]) return element();
				node = t[node][0];
				r = mid;
			}
			else {
				if (!t[node][1]) return element();
				node = t[node][1];
				l = mid + 1;
			}
		}
		return t[node].val;
	}
	element query(T l, T r) {
		if (l > r) return element();
		return query(l, r, 1, L, R);
	}
	element query(T l, T r, int node, T nl, T nr) {
		if (r < nl || nr < l) return element();
		if (l <= nl && nr <= r) return t[node].val;
		T mid = (nl + nr) / 2;
		if (r <= mid || !t[node][1]) {
			if (!t[node][0]) return element();
			return query(l, r, t[node][0], nl, mid);
		}
		if (mid < l || !t[node][0])
			return query(l, r, t[node][1], mid + 1, nr);
		return query(l, r, t[node][0], nl, mid) * query(l, r, t[node][1], mid + 1, nr);
	}
};
 
template<typename element>
struct segtree2D {
	using T = int;
	struct node {
		segtree<element> val;
		int l, r;
		node() {}
		node(T L, T R) {
			l = -1, r = -1;
			val = segtree<element>(L, R);
		}
	};
	T L0, R0, L1, R1;
	vector<node> t;
	segtree2D() {}
	segtree2D(T l0, T r0, T l1, T r1) : L0(l0), R0(r0), L1(l1), R1(r1) {
		t.push_back(node(L1, R1));
	}
	int add_node() {
		t.push_back(node(L1, R1));
		return (int)t.size() - 1;
	}
	int go_left(int v) {
		if (t[v].l == -1) {
			int x = add_node(); // prevents bug from reallocation
			t[v].l = x;
		}
		return t[v].l;
	}
	int go_right(int v) {
		if (t[v].r == -1) {
			int x = add_node(); // prevents bug from reallocation
			t[v].r = x;
		}
		return t[v].r;
	}
	void fix(int node, T pos1) {
		// assumes node has at least 1 child
		element val;
		if (t[node].l == -1) val = t[t[node].r].val.get(pos1);
		else if (t[node].r == -1) val = t[t[node].l].val.get(pos1);
		else val = t[t[node].l].val.get(pos1) * t[t[node].r].val.get(pos1);
		t[node].val.update(pos1, val);
	}
	void update(T pos0, T pos1, element val) {
		update(pos0, pos1, val, 0, L0, R0);
	}
	void update(T pos0, T pos1, element val, int node, T nl, T nr) {
		if (nl == nr) {
			t[node].val.update(pos1, val);
			return;
		}
		T mid = (nl + nr) / 2;
		if (pos0 <= mid) update(pos0, pos1, val, go_left(node), nl, mid);
		else update(pos0, pos1, val, go_right(node), mid + 1, nr);
		fix(node, pos1);
	}
	element query(T l0, T r0, T l1, T r1) {
		if (l0 > r0 || l1 > r1) return element();
		return query(l0, r0, l1, r1, 0, L0, R0);
	}
	element query(T l0, T r0, T l1, T r1, int node, T nl, T nr) {
		if (r0 < nl || nr < l0) return element();
		if (l0 <= nl && nr <= r0) {
			return t[node].val.query(l1, r1);
		}
		T mid = (nl + nr) / 2;
		if (r0 <= mid || t[node].r == -1) {
			if (t[node].l == -1) return element();
			return query(l0, r0, l1, r1, t[node].l, nl, mid);
		}
		if (mid < l0 || t[node].l == -1)
			return query(l0, r0, l1, r1, t[node].r, mid + 1, nr);
		return query(l0, r0, l1, r1, t[node].l, nl, mid) * query(l0, r0, l1, r1, t[node].r, mid + 1, nr);
	}
};
 
ll gcd(ll x, ll y) {
	return !y ? x : gcd(y, x % y);
}
 
struct ele {
	ll x;
	ele(ll xx = 0) : x(xx) {}
	ele operator * (const ele &a) const {
		return ele(gcd(x, a.x));
	}
};
 
segtree2D<ele> T;
 
void init(int R, int C) {
	T = segtree2D<ele>(0, R - 1, 0, C - 1);
}
 
void update(int p, int q, ll k) {
	T.update(p, q, k);
}
 
ll calculate(int p, int q, int u, int v) {
	return T.query(p, u, q, v).x;
}

Compilation message

game.cpp: In instantiation of 'segtree<element>::node::node(element) [with element = ele]':
game.cpp:32:15:   required from 'segtree<element>::segtree(segtree<element>::T, segtree<element>::T) [with element = ele; segtree<element>::T = int]'
game.cpp:108:10:   required from 'segtree2D<element>::node::node(segtree2D<element>::T, segtree2D<element>::T) [with element = ele; segtree2D<element>::T = int]'
game.cpp:115:15:   required from 'segtree2D<element>::segtree2D(segtree2D<element>::T, segtree2D<element>::T, segtree2D<element>::T, segtree2D<element>::T) [with element = ele; segtree2D<element>::T = int]'
game.cpp:191:39:   required from here
game.cpp:21:7: warning: 'segtree<ele>::node::c' will be initialized after [-Wreorder]
   21 |   int c[2];
      |       ^
game.cpp:20:11: warning:   'ele segtree<ele>::node::val' [-Wreorder]
   20 |   element val;
      |           ^~~
game.cpp:22:3: warning:   when initialized here [-Wreorder]
   22 |   node(element v = element()) : c({ 0,0 }), val(v) {}
      |   ^~~~
game.cpp:22:50: warning: list-initializer for non-class type must not be parenthesized
   22 |   node(element v = element()) : c({ 0,0 }), val(v) {}
      |                                                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 436 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 305 ms 12368 KB Output is correct
5 Correct 205 ms 12468 KB Output is correct
6 Correct 253 ms 9348 KB Output is correct
7 Correct 269 ms 8884 KB Output is correct
8 Correct 207 ms 7368 KB Output is correct
9 Correct 257 ms 9524 KB Output is correct
10 Correct 223 ms 5812 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 431 ms 12780 KB Output is correct
13 Correct 695 ms 4692 KB Output is correct
14 Correct 146 ms 1052 KB Output is correct
15 Correct 781 ms 6500 KB Output is correct
16 Correct 120 ms 13988 KB Output is correct
17 Correct 418 ms 9048 KB Output is correct
18 Correct 637 ms 14216 KB Output is correct
19 Correct 556 ms 14420 KB Output is correct
20 Correct 496 ms 13824 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 284 ms 9880 KB Output is correct
13 Correct 218 ms 10224 KB Output is correct
14 Correct 275 ms 6844 KB Output is correct
15 Correct 261 ms 6328 KB Output is correct
16 Correct 183 ms 5068 KB Output is correct
17 Correct 273 ms 6976 KB Output is correct
18 Correct 220 ms 6068 KB Output is correct
19 Correct 471 ms 13020 KB Output is correct
20 Correct 681 ms 4688 KB Output is correct
21 Correct 163 ms 852 KB Output is correct
22 Correct 801 ms 6512 KB Output is correct
23 Correct 123 ms 13904 KB Output is correct
24 Correct 424 ms 9056 KB Output is correct
25 Correct 606 ms 14124 KB Output is correct
26 Correct 559 ms 14416 KB Output is correct
27 Correct 541 ms 13656 KB Output is correct
28 Correct 518 ms 147336 KB Output is correct
29 Correct 1032 ms 162660 KB Output is correct
30 Correct 1782 ms 117624 KB Output is correct
31 Correct 1681 ms 94880 KB Output is correct
32 Correct 239 ms 1104 KB Output is correct
33 Correct 352 ms 3668 KB Output is correct
34 Correct 370 ms 160188 KB Output is correct
35 Correct 648 ms 81476 KB Output is correct
36 Correct 1130 ms 160252 KB Output is correct
37 Correct 984 ms 160200 KB Output is correct
38 Correct 964 ms 159812 KB Output is correct
39 Correct 819 ms 124304 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 283 ms 9892 KB Output is correct
13 Correct 192 ms 10156 KB Output is correct
14 Correct 241 ms 6800 KB Output is correct
15 Correct 262 ms 6328 KB Output is correct
16 Correct 181 ms 5068 KB Output is correct
17 Correct 263 ms 6968 KB Output is correct
18 Correct 221 ms 5816 KB Output is correct
19 Correct 442 ms 12956 KB Output is correct
20 Correct 715 ms 4636 KB Output is correct
21 Correct 139 ms 872 KB Output is correct
22 Correct 816 ms 6480 KB Output is correct
23 Correct 114 ms 13904 KB Output is correct
24 Correct 415 ms 9044 KB Output is correct
25 Correct 600 ms 14164 KB Output is correct
26 Correct 542 ms 14452 KB Output is correct
27 Correct 502 ms 13856 KB Output is correct
28 Correct 454 ms 147372 KB Output is correct
29 Correct 942 ms 162488 KB Output is correct
30 Correct 1765 ms 117616 KB Output is correct
31 Correct 1687 ms 95180 KB Output is correct
32 Correct 236 ms 1104 KB Output is correct
33 Correct 349 ms 3728 KB Output is correct
34 Correct 403 ms 159940 KB Output is correct
35 Correct 630 ms 81460 KB Output is correct
36 Correct 1160 ms 160188 KB Output is correct
37 Correct 1028 ms 160228 KB Output is correct
38 Correct 950 ms 159812 KB Output is correct
39 Runtime error 615 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -