oj.uz

Submission #1113064

# Submission time Handle Problem Language Result Execution time Memory
1113064 2024-11-15T15:43:58 Z Noam527 Game (IOI13_game) C++17
80 / 100
 2550 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"
 
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;
	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) {
		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, T... nxt) {
		return upd(x, 0, 0, N, 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(T... nxt) {
		return que(0, 0, N, 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 2 ms 760 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 2 ms 592 KB Output is correct
10 Correct 1 ms 488 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 1 ms 336 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 609 ms 33732 KB Output is correct
5 Correct 426 ms 32948 KB Output is correct
6 Correct 548 ms 31228 KB Output is correct
7 Correct 602 ms 30652 KB Output is correct
8 Correct 403 ms 20912 KB Output is correct
9 Correct 590 ms 30448 KB Output is correct
10 Correct 566 ms 30352 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 336 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 1 ms 504 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 2 ms 592 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 813 ms 18712 KB Output is correct
13 Correct 1061 ms 10492 KB Output is correct
14 Correct 346 ms 5704 KB Output is correct
15 Correct 1143 ms 13792 KB Output is correct
16 Correct 366 ms 21064 KB Output is correct
17 Correct 732 ms 16724 KB Output is correct
18 Correct 1164 ms 22584 KB Output is correct
19 Correct 1061 ms 22848 KB Output is correct
20 Correct 989 ms 22088 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 544 KB Output is correct
3 Correct 2 ms 760 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 2 ms 592 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 611 ms 33836 KB Output is correct
13 Correct 486 ms 32956 KB Output is correct
14 Correct 574 ms 31088 KB Output is correct
15 Correct 569 ms 30652 KB Output is correct
16 Correct 365 ms 20772 KB Output is correct
17 Correct 547 ms 30720 KB Output is correct
18 Correct 513 ms 30400 KB Output is correct
19 Correct 813 ms 18808 KB Output is correct
20 Correct 1064 ms 10428 KB Output is correct
21 Correct 355 ms 5684 KB Output is correct
22 Correct 1186 ms 13896 KB Output is correct
23 Correct 391 ms 21188 KB Output is correct
24 Correct 796 ms 16724 KB Output is correct
25 Correct 1180 ms 22776 KB Output is correct
26 Correct 1008 ms 22888 KB Output is correct
27 Correct 946 ms 22088 KB Output is correct
28 Correct 506 ms 155632 KB Output is correct
29 Correct 1097 ms 171192 KB Output is correct
30 Correct 2478 ms 123412 KB Output is correct
31 Correct 2449 ms 101380 KB Output is correct
32 Correct 294 ms 10348 KB Output is correct
33 Correct 429 ms 12624 KB Output is correct
34 Correct 614 ms 165232 KB Output is correct
35 Correct 766 ms 90556 KB Output is correct
36 Correct 1500 ms 169116 KB Output is correct
37 Correct 1339 ms 169360 KB Output is correct
38 Correct 1276 ms 168784 KB Output is correct
39 Correct 1107 ms 132956 KB Output is correct
40 Correct 1 ms 336 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 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 336 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 546 ms 33704 KB Output is correct
13 Correct 428 ms 32956 KB Output is correct
14 Correct 553 ms 31060 KB Output is correct
15 Correct 564 ms 30600 KB Output is correct
16 Correct 384 ms 20748 KB Output is correct
17 Correct 658 ms 30564 KB Output is correct
18 Correct 638 ms 30408 KB Output is correct
19 Correct 858 ms 18852 KB Output is correct
20 Correct 1049 ms 10388 KB Output is correct
21 Correct 345 ms 5800 KB Output is correct
22 Correct 1183 ms 13924 KB Output is correct
23 Correct 373 ms 21064 KB Output is correct
24 Correct 748 ms 16712 KB Output is correct
25 Correct 1151 ms 22744 KB Output is correct
26 Correct 1107 ms 22856 KB Output is correct
27 Correct 999 ms 22088 KB Output is correct
28 Correct 537 ms 155884 KB Output is correct
29 Correct 1161 ms 171152 KB Output is correct
30 Correct 2550 ms 123544 KB Output is correct
31 Correct 2344 ms 101436 KB Output is correct
32 Correct 301 ms 10500 KB Output is correct
33 Correct 442 ms 12680 KB Output is correct
34 Correct 686 ms 165288 KB Output is correct
35 Correct 822 ms 90420 KB Output is correct
36 Correct 1474 ms 169176 KB Output is correct
37 Correct 1279 ms 169396 KB Output is correct
38 Correct 1250 ms 168988 KB Output is correct
39 Runtime error 648 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -