oj.uz

Submission #1087910

# Submission time Handle Problem Language Result Execution time Memory
1087910 2024-09-13T13:07:16 Z Noam527 Game (IOI13_game) C++17
100 / 100
 1772 ms 157872 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 c[2];
		node() {}
		node(T L, T R) : c({0, 0}), val(L, R) {}
		int& operator [](int i) {
			return c[i];
		}
	};
	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()); // dummy
		t.push_back(node(L1, R1)); // root
	}
	int add_node() {
		t.push_back(node(L1, R1));
		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 node, T pos1) {
		// assumes node has at least 1 child
		element val;
		if (!t[node][0]) val = t[t[node][1]].val.get(pos1);
		else if (!t[node][1]) val = t[t[node][0]].val.get(pos1);
		else val = t[t[node][0]].val.get(pos1) * t[t[node][1]].val.get(pos1);
		t[node].val.update(pos1, val);
	}
	void update(T pos0, T pos1, element val) {
		update(pos0, pos1, val, 1, 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(node, 0), nl, mid);
		else update(pos0, pos1, val, go(node, 1), 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, 1, 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][1]) {
			if (!t[node][0]) return element();
			return query(l0, r0, l1, r1, t[node][0], nl, mid);
		}
		if (mid < l0 || !t[node][0])
			return query(l0, r0, l1, r1, t[node][1], mid + 1, nr);
		return query(l0, r0, l1, r1, t[node][0], nl, mid) * query(l0, r0, l1, r1, t[node][1], 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 'segtree2D<element>::node::node(segtree2D<element>::T, segtree2D<element>::T) [with element = ele; segtree2D<element>::T = int]':
game.cpp:155: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:224:39:   required from here
game.cpp:143:7: warning: 'segtree2D<ele>::node::c' will be initialized after [-Wreorder]
  143 |   int c[2];
      |       ^
game.cpp:142:20: warning:   'segtree<ele> segtree2D<ele>::node::val' [-Wreorder]
  142 |   segtree<element> val;
      |                    ^~~
game.cpp:145:3: warning:   when initialized here [-Wreorder]
  145 |   node(T L, T R) : c({0, 0}), val(L, R) {}
      |   ^~~~
game.cpp:145:39: warning: list-initializer for non-class type must not be parenthesized
  145 |   node(T L, T R) : c({0, 0}), val(L, R) {}
      |                                       ^
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:145:39:   required from 'segtree2D<element>::node::node(segtree2D<element>::T, segtree2D<element>::T) [with element = ele; segtree2D<element>::T = int]'
game.cpp:155: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:224: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 1 ms 344 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 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.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 284 ms 14464 KB Output is correct
5 Correct 213 ms 14216 KB Output is correct
6 Correct 251 ms 11196 KB Output is correct
7 Correct 271 ms 11292 KB Output is correct
8 Correct 184 ms 9476 KB Output is correct
9 Correct 260 ms 11220 KB Output is correct
10 Correct 226 ms 10680 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 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 425 ms 13188 KB Output is correct
13 Correct 740 ms 7508 KB Output is correct
14 Correct 146 ms 5548 KB Output is correct
15 Correct 841 ms 8648 KB Output is correct
16 Correct 104 ms 10912 KB Output is correct
17 Correct 445 ms 9596 KB Output is correct
18 Correct 633 ms 12520 KB Output is correct
19 Correct 565 ms 12716 KB Output is correct
20 Correct 531 ms 11936 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 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 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 344 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 432 KB Output is correct
12 Correct 297 ms 14464 KB Output is correct
13 Correct 200 ms 14256 KB Output is correct
14 Correct 287 ms 11192 KB Output is correct
15 Correct 281 ms 11300 KB Output is correct
16 Correct 185 ms 9460 KB Output is correct
17 Correct 269 ms 11188 KB Output is correct
18 Correct 229 ms 10680 KB Output is correct
19 Correct 445 ms 13332 KB Output is correct
20 Correct 709 ms 7248 KB Output is correct
21 Correct 140 ms 5460 KB Output is correct
22 Correct 842 ms 8960 KB Output is correct
23 Correct 101 ms 10924 KB Output is correct
24 Correct 441 ms 9572 KB Output is correct
25 Correct 646 ms 12360 KB Output is correct
26 Correct 567 ms 12708 KB Output is correct
27 Correct 539 ms 12052 KB Output is correct
28 Correct 372 ms 65208 KB Output is correct
29 Correct 776 ms 71852 KB Output is correct
30 Correct 1263 ms 80928 KB Output is correct
31 Correct 1144 ms 70344 KB Output is correct
32 Correct 189 ms 10260 KB Output is correct
33 Correct 295 ms 10452 KB Output is correct
34 Correct 201 ms 66228 KB Output is correct
35 Correct 573 ms 39200 KB Output is correct
36 Correct 984 ms 69288 KB Output is correct
37 Correct 843 ms 69816 KB Output is correct
38 Correct 815 ms 69004 KB Output is correct
39 Correct 741 ms 66760 KB Output is correct
40 Correct 1 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 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 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 317 ms 14520 KB Output is correct
13 Correct 219 ms 14256 KB Output is correct
14 Correct 252 ms 11192 KB Output is correct
15 Correct 279 ms 11452 KB Output is correct
16 Correct 207 ms 9404 KB Output is correct
17 Correct 272 ms 11236 KB Output is correct
18 Correct 242 ms 10844 KB Output is correct
19 Correct 431 ms 12964 KB Output is correct
20 Correct 722 ms 7092 KB Output is correct
21 Correct 137 ms 5456 KB Output is correct
22 Correct 834 ms 8760 KB Output is correct
23 Correct 98 ms 11012 KB Output is correct
24 Correct 436 ms 9648 KB Output is correct
25 Correct 620 ms 12528 KB Output is correct
26 Correct 581 ms 12780 KB Output is correct
27 Correct 553 ms 11912 KB Output is correct
28 Correct 372 ms 65204 KB Output is correct
29 Correct 720 ms 71856 KB Output is correct
30 Correct 1278 ms 80884 KB Output is correct
31 Correct 1190 ms 70332 KB Output is correct
32 Correct 177 ms 10228 KB Output is correct
33 Correct 309 ms 10672 KB Output is correct
34 Correct 241 ms 66312 KB Output is correct
35 Correct 590 ms 39300 KB Output is correct
36 Correct 1002 ms 69224 KB Output is correct
37 Correct 827 ms 69904 KB Output is correct
38 Correct 841 ms 69076 KB Output is correct
39 Correct 538 ms 129412 KB Output is correct
40 Correct 1120 ms 143240 KB Output is correct
41 Correct 1772 ms 157872 KB Output is correct
42 Correct 1656 ms 135084 KB Output is correct
43 Correct 388 ms 139144 KB Output is correct
44 Correct 226 ms 10580 KB Output is correct
45 Correct 743 ms 66760 KB Output is correct
46 Correct 1299 ms 142072 KB Output is correct
47 Correct 1351 ms 141700 KB Output is correct
48 Correct 1254 ms 141488 KB Output is correct
49 Correct 0 ms 348 KB Output is correct