oj.uz

Submission #569784

# Submission time Handle Problem Language Result Execution time Memory
569784 2022-05-27T19:19:45 Z Noam527 Game (IOI13_game) C++17
100 / 100
 2960 ms 154664 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"
 
/*
the struct 'element' must have:
* neutral element (as default constructor)
* operator *, to combine with a right operand and return the result
note the "using T = ll". this is the range of indicies we allow. can change to int for efficiency.
note the static constant LIM. used for efficiency of both time and memory. practice shows that 64 or 128 are the best.
this entire thing assumes commutativity (which is acceptable since the order of operations is weird in 2D).
*/
template<typename element>
struct segtree {
	using T = int;
	struct node {
		element val;
		int l, r;
		node(element v = element()) {
			l = -1, r = -1, val = v;
		}
	};
	T L, R;
	vector<node> t;

	// constant optimizations
	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());
		
		big = 0;
		cache_i = L;
		cache_v = element();
	}
	int add_node() {
		t.push_back(node());
		return (int)t.size() - 1;
	}
	int go_left(int v) {
		if (t[v].l == -1) {
			// this prevents a bug that might occur when t.push_back provokes reallocation
			int x = add_node();
			t[v].l = x;
		}
		return t[v].l;
	}
	int go_right(int v) {
		if (t[v].r == -1) {
			// this prevents a bug that might occur when t.push_back provokes reallocation
			int x = add_node();
			t[v].r = x;
		}
		return t[v].r;
	}
	void fix(int v) {
		// assumes v has at least 1 child
		if (t[v].l == -1) t[v].val = t[t[v].r].val;
		else if (t[v].r == -1) t[v].val = t[t[v].l].val;
		else t[v].val = t[t[v].l].val * t[t[v].r].val;
	}
	void update(T pos, element val) {
		cache_i = pos;
		cache_v = val;
		if (big) {
			update(pos, val, 0, 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, 0, 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_left(node), nl, mid);
		else update(pos, val, go_right(node), mid + 1, nr);
		fix(node);
	}
	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 = 0;
		T l = L, r = R;
		while (l < r) {
			T mid = (l + r) / 2;
			if (i <= mid) {
				if (t[node].l == -1) return element();
				node = t[node].l;
				r = mid;
			}
			else {
				if (t[node].r == -1) return element();
				node = t[node].r;
				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, 0, 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].r == -1) {
			if (t[node].l == -1) return element();
			return query(l, r, t[node].l, nl, mid);
		}
		if (mid < l || t[node].l == -1)
			return query(l, r, t[node].r, mid + 1, nr);
		return query(l, r, t[node].l, nl, mid) * query(l, r, t[node].r, 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) {
			// this prevents a bug that might occur when t.push_back provokes reallocation
			int x = add_node();
			t[v].l = x;
		}
		return t[v].l;
	}
	int go_right(int v) {
		if (t[v].r == -1) {
			// this prevents a bug that might occur when t.push_back provokes reallocation
			int x = add_node();
			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);
		//cout << "<outer> inside fix, updating " << node << " at " << pos1 << " with " << val.x << '\n';
		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) {
			//cout << "<outer> updating " << node << " at " << pos1 << " with " << val.x << '\n';
			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);
		//cout << "<outer> fixing " << node << " at " << pos1 << '\n';
		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) {
			//cout << "<outer> querying " << node << " at [" << nl << ", " << nr << "] with [" << l1 << ", " << r1 << "]\n";
			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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 300 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 415 ms 11668 KB Output is correct
5 Correct 327 ms 11884 KB Output is correct
6 Correct 338 ms 8104 KB Output is correct
7 Correct 358 ms 8192 KB Output is correct
8 Correct 260 ms 6708 KB Output is correct
9 Correct 376 ms 8348 KB Output is correct
10 Correct 316 ms 7528 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 653 ms 10308 KB Output is correct
13 Correct 1252 ms 4836 KB Output is correct
14 Correct 250 ms 2452 KB Output is correct
15 Correct 1488 ms 5840 KB Output is correct
16 Correct 157 ms 8088 KB Output is correct
17 Correct 583 ms 6312 KB Output is correct
18 Correct 834 ms 8740 KB Output is correct
19 Correct 764 ms 8684 KB Output is correct
20 Correct 716 ms 8072 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 411 ms 11752 KB Output is correct
13 Correct 332 ms 11804 KB Output is correct
14 Correct 370 ms 8116 KB Output is correct
15 Correct 370 ms 8204 KB Output is correct
16 Correct 277 ms 6732 KB Output is correct
17 Correct 398 ms 8492 KB Output is correct
18 Correct 309 ms 7604 KB Output is correct
19 Correct 624 ms 10504 KB Output is correct
20 Correct 1244 ms 4660 KB Output is correct
21 Correct 229 ms 2380 KB Output is correct
22 Correct 1494 ms 5980 KB Output is correct
23 Correct 174 ms 8180 KB Output is correct
24 Correct 575 ms 6284 KB Output is correct
25 Correct 861 ms 8660 KB Output is correct
26 Correct 754 ms 8684 KB Output is correct
27 Correct 715 ms 8092 KB Output is correct
28 Correct 529 ms 53212 KB Output is correct
29 Correct 955 ms 60008 KB Output is correct
30 Correct 2128 ms 73868 KB Output is correct
31 Correct 1941 ms 63476 KB Output is correct
32 Correct 287 ms 2056 KB Output is correct
33 Correct 479 ms 2560 KB Output is correct
34 Correct 300 ms 58184 KB Output is correct
35 Correct 784 ms 29080 KB Output is correct
36 Correct 1340 ms 57092 KB Output is correct
37 Correct 1162 ms 57924 KB Output is correct
38 Correct 1123 ms 57164 KB Output is correct
39 Correct 972 ms 56460 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 400 ms 11756 KB Output is correct
13 Correct 313 ms 11840 KB Output is correct
14 Correct 350 ms 8076 KB Output is correct
15 Correct 380 ms 8200 KB Output is correct
16 Correct 252 ms 6840 KB Output is correct
17 Correct 366 ms 8344 KB Output is correct
18 Correct 332 ms 7596 KB Output is correct
19 Correct 634 ms 10380 KB Output is correct
20 Correct 1269 ms 4796 KB Output is correct
21 Correct 244 ms 2396 KB Output is correct
22 Correct 1475 ms 5908 KB Output is correct
23 Correct 168 ms 8260 KB Output is correct
24 Correct 614 ms 6204 KB Output is correct
25 Correct 823 ms 8696 KB Output is correct
26 Correct 777 ms 8840 KB Output is correct
27 Correct 736 ms 8020 KB Output is correct
28 Correct 516 ms 53148 KB Output is correct
29 Correct 949 ms 59872 KB Output is correct
30 Correct 2121 ms 73844 KB Output is correct
31 Correct 1925 ms 63480 KB Output is correct
32 Correct 287 ms 2088 KB Output is correct
33 Correct 464 ms 2540 KB Output is correct
34 Correct 303 ms 58424 KB Output is correct
35 Correct 752 ms 29172 KB Output is correct
36 Correct 1326 ms 57236 KB Output is correct
37 Correct 1194 ms 57692 KB Output is correct
38 Correct 1125 ms 57052 KB Output is correct
39 Correct 781 ms 124096 KB Output is correct
40 Correct 1550 ms 139228 KB Output is correct
41 Correct 2960 ms 154664 KB Output is correct
42 Correct 2711 ms 133152 KB Output is correct
43 Correct 557 ms 134212 KB Output is correct
44 Correct 358 ms 10432 KB Output is correct
45 Correct 1054 ms 65236 KB Output is correct
46 Correct 1886 ms 137220 KB Output is correct
47 Correct 1933 ms 137052 KB Output is correct
48 Correct 1925 ms 136412 KB Output is correct
49 Correct 1 ms 212 KB Output is correct