oj.uz

Submission #1087556

# Submission time Handle Problem Language Result Execution time Memory
1087556 2024-09-12T23:34:03 Z Noam527 Game (IOI13_game) C++17
100 / 100
 1740 ms 158108 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;
	static const int LIM = 64;
	vector<pair<T, element>> last;
	bool big;
	T cache_i;
	element cache_v;

	segtree() {}
	segtree(T LL, T RR) : L(LL), R(RR) {
		t.push_back(node()); // dummy
		t.push_back(node()); // root
		big = 0;
		cache_i = L;
		cache_v = element();
	}
	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) {
		cache_i = pos, cache_v = val;
		if (big) {
			update(pos, val, 1, L, R);
			return;
		}
		bool found = false;
		for (auto& i : last) {
			if (i.first == pos) {
				i.second = val;
				found = true;
				break;
			}
		}
		if (!found) last.emplace_back(pos, val);
		if (last.size() < LIM) return;
		for (const auto& i : last)
			update(i.first, i.second, 1, L, R);
		last.clear();
		big = 1;
	}
	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) {
		if (i == cache_i) return cache_v;
		if (!big) {
			for (const auto& j : last)
				if (j.first == i) return j.second;
			return element();
		}
		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();
		if (!big) {
			element res;
			for (const auto& i : last)
				if (l <= i.first && i.first <= r)
					res = res * i.second;
			return res;
		}
		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:37:15:   required from 'segtree<element>::segtree(segtree<element>::T, segtree<element>::T) [with element = ele; segtree<element>::T = int]'
game.cpp:147:10:   required from 'segtree2D<element>::node::node(segtree2D<element>::T, segtree2D<element>::T) [with element = ele; segtree2D<element>::T = int]'
game.cpp:154: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:230: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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 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 388 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 1 ms 348 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 1 ms 348 KB Output is correct
4 Correct 286 ms 14516 KB Output is correct
5 Correct 217 ms 14260 KB Output is correct
6 Correct 246 ms 11136 KB Output is correct
7 Correct 265 ms 11444 KB Output is correct
8 Correct 190 ms 9692 KB Output is correct
9 Correct 259 ms 11416 KB Output is correct
10 Correct 225 ms 10680 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 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 1 ms 600 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 427 ms 12904 KB Output is correct
13 Correct 717 ms 7236 KB Output is correct
14 Correct 177 ms 5460 KB Output is correct
15 Correct 860 ms 8764 KB Output is correct
16 Correct 106 ms 11024 KB Output is correct
17 Correct 432 ms 9644 KB Output is correct
18 Correct 622 ms 12464 KB Output is correct
19 Correct 600 ms 12720 KB Output is correct
20 Correct 527 ms 12096 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 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 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 295 ms 14644 KB Output is correct
13 Correct 198 ms 14260 KB Output is correct
14 Correct 247 ms 11216 KB Output is correct
15 Correct 267 ms 11352 KB Output is correct
16 Correct 192 ms 9560 KB Output is correct
17 Correct 262 ms 11308 KB Output is correct
18 Correct 245 ms 10680 KB Output is correct
19 Correct 428 ms 13084 KB Output is correct
20 Correct 731 ms 7244 KB Output is correct
21 Correct 140 ms 5460 KB Output is correct
22 Correct 846 ms 8884 KB Output is correct
23 Correct 102 ms 10928 KB Output is correct
24 Correct 438 ms 9648 KB Output is correct
25 Correct 616 ms 12464 KB Output is correct
26 Correct 569 ms 12976 KB Output is correct
27 Correct 532 ms 12088 KB Output is correct
28 Correct 408 ms 65288 KB Output is correct
29 Correct 714 ms 71856 KB Output is correct
30 Correct 1339 ms 80840 KB Output is correct
31 Correct 1140 ms 70340 KB Output is correct
32 Correct 190 ms 10068 KB Output is correct
33 Correct 295 ms 10668 KB Output is correct
34 Correct 203 ms 66224 KB Output is correct
35 Correct 567 ms 39284 KB Output is correct
36 Correct 957 ms 69292 KB Output is correct
37 Correct 829 ms 69892 KB Output is correct
38 Correct 783 ms 69176 KB Output is correct
39 Correct 707 ms 66784 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 280 ms 14812 KB Output is correct
13 Correct 205 ms 14264 KB Output is correct
14 Correct 242 ms 11192 KB Output is correct
15 Correct 268 ms 11436 KB Output is correct
16 Correct 183 ms 9412 KB Output is correct
17 Correct 271 ms 11432 KB Output is correct
18 Correct 223 ms 10704 KB Output is correct
19 Correct 422 ms 13144 KB Output is correct
20 Correct 731 ms 7252 KB Output is correct
21 Correct 171 ms 5532 KB Output is correct
22 Correct 853 ms 8876 KB Output is correct
23 Correct 114 ms 10928 KB Output is correct
24 Correct 444 ms 9584 KB Output is correct
25 Correct 616 ms 12444 KB Output is correct
26 Correct 578 ms 12620 KB Output is correct
27 Correct 544 ms 12212 KB Output is correct
28 Correct 365 ms 65296 KB Output is correct
29 Correct 689 ms 71856 KB Output is correct
30 Correct 1257 ms 80748 KB Output is correct
31 Correct 1170 ms 70336 KB Output is correct
32 Correct 195 ms 10128 KB Output is correct
33 Correct 293 ms 10672 KB Output is correct
34 Correct 194 ms 66220 KB Output is correct
35 Correct 575 ms 39268 KB Output is correct
36 Correct 954 ms 69296 KB Output is correct
37 Correct 849 ms 69804 KB Output is correct
38 Correct 795 ms 69040 KB Output is correct
39 Correct 519 ms 129412 KB Output is correct
40 Correct 1106 ms 143292 KB Output is correct
41 Correct 1740 ms 158108 KB Output is correct
42 Correct 1643 ms 135084 KB Output is correct
43 Correct 368 ms 139208 KB Output is correct
44 Correct 234 ms 10604 KB Output is correct
45 Correct 730 ms 66760 KB Output is correct
46 Correct 1356 ms 142244 KB Output is correct
47 Correct 1304 ms 141700 KB Output is correct
48 Correct 1221 ms 141412 KB Output is correct
49 Correct 0 ms 348 KB Output is correct