oj.uz

Submission #1113071

# Submission time Handle Problem Language Result Execution time Memory
1113071 2024-11-15T16:08:35 Z Noam527 Game (IOI13_game) C++17
100 / 100
 2130 ms 150768 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"
 
template<int D, typename element, ll N>
struct segtree {
	template<int d> using sdim = segtree<d, element, N>;
#define mid (nl + (nr - nl) / 2) // IMP: undef in the end
#define templatic template<class... T>
	struct node {
		int c[2];
		sdim<D - 1> val;
		node() { c[0] = c[1] = 0; }
		int& operator[](int i) { return c[i]; };
	};
	vector<node> t;
	static constexpr int LIM = (D == 1) * 64; // 64 or 128
	vector<pair<ll, element>> cache;

	segtree() : t(1) {}
	int add_node() {
		t.push_back(node());
		return (int)t.size() - 1;
	}
	int go(int n, int d) {
		if (!t[n][d]) {
			int x = add_node();
			t[n][d] = x;
		}
		return t[n][d];
	}
	templatic element get(ll i, T... nxt) {
		if (t.size() == 1) {
			element res;
			for (auto& x : cache)
				if (x.first == i) res = x.second;
			return res;
		}
		int n = 0; ll l = 0, r = N, m;
		do {
			m = l + (r - l) / 2;
			if (i < m) n = t[n][0], r = m;
			else n = t[n][1], l = m;
		} while (n && l + 1 < r);
		if (!n) return element();
		return t[n].val.get(nxt...);
	}
	templatic element update(element x, ll i, T... nxt) {
		if (t.size() == 1) {
			bool found = false;
			for (auto& v : cache)
				if (v.first == i) v.second = x, found = true;
			if (!found) cache.emplace_back(i, x);
			if (cache.size() < LIM) return x;
			for (auto& v : cache)
				upd(v.second, 0, 0, N, v.first, nxt...);
			return cache.clear(), x;
		}
		return upd(x, 0, 0, N, i, nxt...);
	}
	templatic element upd(element x, ll n, ll nl, ll nr, ll i, T... nxt) {
		if (nl + 1 == nr) return t[n].val.update(x, nxt...) , x;
		int d = i >= mid;
		(i < mid ? nr : nl) = mid;
		element lx = upd(x, go(n, d), nl, nr, i, nxt...), rx;
		if (t[n][!d]) rx = t[t[n][!d]].val.get(nxt...);
		return t[n].val.update(lx * rx, nxt...) , lx * rx;
	}
	templatic element query(ll l, ll r, T... nxt) {
		if (t.size() == 1) {
			element res;
			for (auto& x : cache)
				if (l <= x.first && x.first < r)
					res = res * x.second;
			return res;
		}
		return que(0, 0, N, l, r, nxt...);
	}
	templatic element que(ll n, ll nl, ll nr, ll l, ll r, T... nxt) {
		if (nr <= l || r <= nl) return element();
		if (l <= nl && nr <= r) return t[n].val.query(nxt...);
		return (t[n][0] ? que(t[n][0], nl, mid, l, r, nxt...) : element()) *
			(t[n][1] ? que(t[n][1], mid, nr, l, r, nxt...) : element());
	}
};
template<typename element, ll N>
struct segtree<0, element, N> {
	element val;
	segtree() {}
	element get() { return val; }
	element query() { return val; }
	element update(element x) {
		return val = x;
	}
};
 
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));
	}
};
 
segtree<2, ele, 1000000005> T;
 
void init(int R, int C) {
	// nothing...
}
 
void update(int p, int q, ll k) {
	T.update(ele(k), p, q);
}
 
ll calculate(int p, int q, int u, int v) {
	return T.query(p, u + 1, q, v + 1).x;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 504 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 601 ms 31860 KB Output is correct
5 Correct 505 ms 31432 KB Output is correct
6 Correct 623 ms 28868 KB Output is correct
7 Correct 633 ms 30916 KB Output is correct
8 Correct 411 ms 18992 KB Output is correct
9 Correct 632 ms 28744 KB Output is correct
10 Correct 582 ms 30744 KB Output is correct
11 Correct 1 ms 336 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 448 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 622 ms 12832 KB Output is correct
13 Correct 969 ms 7324 KB Output is correct
14 Correct 180 ms 3400 KB Output is correct
15 Correct 1089 ms 8124 KB Output is correct
16 Correct 388 ms 11804 KB Output is correct
17 Correct 625 ms 8568 KB Output is correct
18 Correct 940 ms 11372 KB Output is correct
19 Correct 899 ms 11592 KB Output is correct
20 Correct 834 ms 12180 KB Output is correct
21 Correct 1 ms 336 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 508 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 624 ms 33092 KB Output is correct
13 Correct 468 ms 31484 KB Output is correct
14 Correct 583 ms 30148 KB Output is correct
15 Correct 550 ms 30916 KB Output is correct
16 Correct 374 ms 20296 KB Output is correct
17 Correct 562 ms 30108 KB Output is correct
18 Correct 578 ms 29636 KB Output is correct
19 Correct 689 ms 13644 KB Output is correct
20 Correct 1002 ms 7752 KB Output is correct
21 Correct 189 ms 4656 KB Output is correct
22 Correct 1070 ms 8144 KB Output is correct
23 Correct 387 ms 10344 KB Output is correct
24 Correct 619 ms 9800 KB Output is correct
25 Correct 979 ms 11644 KB Output is correct
26 Correct 895 ms 11424 KB Output is correct
27 Correct 836 ms 10684 KB Output is correct
28 Correct 413 ms 55072 KB Output is correct
29 Correct 770 ms 60412 KB Output is correct
30 Correct 1492 ms 76692 KB Output is correct
31 Correct 1404 ms 67428 KB Output is correct
32 Correct 218 ms 5704 KB Output is correct
33 Correct 373 ms 6240 KB Output is correct
34 Correct 585 ms 53752 KB Output is correct
35 Correct 637 ms 31984 KB Output is correct
36 Correct 1127 ms 53052 KB Output is correct
37 Correct 944 ms 59900 KB Output is correct
38 Correct 884 ms 52164 KB Output is correct
39 Correct 804 ms 57532 KB Output is correct
40 Correct 1 ms 336 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 575 ms 30872 KB Output is correct
13 Correct 469 ms 32936 KB Output is correct
14 Correct 561 ms 26308 KB Output is correct
15 Correct 606 ms 28868 KB Output is correct
16 Correct 408 ms 16664 KB Output is correct
17 Correct 637 ms 26272 KB Output is correct
18 Correct 589 ms 25800 KB Output is correct
19 Correct 681 ms 9524 KB Output is correct
20 Correct 1018 ms 4152 KB Output is correct
21 Correct 194 ms 5704 KB Output is correct
22 Correct 1058 ms 5448 KB Output is correct
23 Correct 388 ms 8264 KB Output is correct
24 Correct 635 ms 5960 KB Output is correct
25 Correct 973 ms 8556 KB Output is correct
26 Correct 867 ms 8776 KB Output is correct
27 Correct 839 ms 8008 KB Output is correct
28 Correct 427 ms 59920 KB Output is correct
29 Correct 764 ms 55432 KB Output is correct
30 Correct 1527 ms 70020 KB Output is correct
31 Correct 1402 ms 60668 KB Output is correct
32 Correct 228 ms 9800 KB Output is correct
33 Correct 352 ms 2420 KB Output is correct
34 Correct 633 ms 52652 KB Output is correct
35 Correct 685 ms 33016 KB Output is correct
36 Correct 1149 ms 51972 KB Output is correct
37 Correct 972 ms 52836 KB Output is correct
38 Correct 854 ms 57348 KB Output is correct
39 Correct 578 ms 115912 KB Output is correct
40 Correct 1178 ms 129980 KB Output is correct
41 Correct 2130 ms 150768 KB Output is correct
42 Correct 1923 ms 133416 KB Output is correct
43 Correct 1010 ms 125904 KB Output is correct
44 Correct 276 ms 10416 KB Output is correct
45 Correct 820 ms 58980 KB Output is correct
46 Correct 1567 ms 128776 KB Output is correct
47 Correct 1632 ms 128460 KB Output is correct
48 Correct 1316 ms 129284 KB Output is correct
49 Correct 1 ms 336 KB Output is correct