oj.uz

Submission #954609

# Submission time Handle Problem Language Result Execution time Memory
954609 2024-03-28T08:14:37 Z islingr Game (IOI13_game) C++17
63 / 100
 2794 ms 15484 KB 
#include "bits/stdc++.h"
#include "game.h"
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
using ll = long long;
using K = array<int, 2>;
 
struct Node {
	Node *l = 0, *r = 0;
 
	ll  v, g;
	K key;
	int y;
	Node(ll val, K key) : v(val), g(val), key(key), y(rng()) {}
	void pull();
};
ll val(Node* n) { return n ? n->g : 0; }
void Node::pull() { g = gcd(val(l), gcd(v, val(r))); }
 
pair<Node*, Node*> split(Node* n, K k) {
	if (!n) return {};
	if (n->key >= k) {
		auto pa = split(n->l, k);
		n->l = pa.second;
		n->pull();
		return {pa.first, n};
	} else {
		auto pa = split(n->r, k);
		n->r = pa.first;
		n->pull();
		return {n, pa.second};
	}
}
 
Node* merge(Node* l, Node* r) {
	if (!l) return r;
	if (!r) return l;
	if (l->y > r->y) {
		l->r = merge(l->r, r);
		l->pull();
		return l;
	} else {
		r->l = merge(l, r->l);
		r->pull();
		return r;
	}
}
 
struct gcd_treap {
	Node* root;
 
	gcd_treap() : root{nullptr} {}
	void set(K k, ll val) {
		Node *L, *X, *R;
		tie(L, X) = split(root, k);
		++k[1];
		tie(X, R) = split(X, k);
		--k[1];
		delete X;
		auto new_node = new Node(val, k);
		root = merge(L, merge(new_node, R));
	}
 
	ll query(int l, int r) {
		const K kl = {l, -1}, kr = {r, -1};
		Node *L, *X, *R;
		tie(L, X) = split(root, kl);
		tie(X, R) = split(X, kr);
		const auto g = val(X);
		root = merge(L, merge(X, R));
		return g;
	}
};
 
struct segtree {
	int sz;
	vector<gcd_treap> t;
 
	segtree() {}
	segtree(int n) : sz{1} {
		while (sz < n) sz *= 2;
		t.resize(2 * sz);
	}
 
	ll query(int l, int r, int u, int d) {
		ll g = 0;
		for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
			if (l & 1) g = gcd(g, t[l++].query(u, d));
			if (r & 1) g = gcd(g, t[--r].query(u, d));
		}
		return g;
	}
 
	void set(int x, int y, ll val) {
		for (int p = x + sz; p > 0; p /= 2)
			t[p].set({y, x}, val);
	}
};
segtree t;
 
void init(int n, int m) { t = segtree(n); }
 
void update(int i, int j, ll val) {
	t.set(i, j, val);
}
 
ll calculate(int l, int u, int r, int d) {
	++r, ++d;
	return t.query(l, r, u, d);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 586 ms 7456 KB Output is correct
5 Correct 266 ms 11584 KB Output is correct
6 Correct 968 ms 9420 KB Output is correct
7 Correct 1074 ms 8936 KB Output is correct
8 Correct 741 ms 7548 KB Output is correct
9 Correct 1058 ms 8864 KB Output is correct
10 Correct 948 ms 8852 KB Output is correct
11 Correct 1 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1024 ms 11328 KB Output is correct
13 Correct 2794 ms 10208 KB Output is correct
14 Correct 497 ms 5876 KB Output is correct
15 Correct 2790 ms 11328 KB Output is correct
16 Correct 870 ms 12904 KB Output is correct
17 Correct 1502 ms 10068 KB Output is correct
18 Correct 2558 ms 14548 KB Output is correct
19 Correct 2147 ms 14584 KB Output is correct
20 Correct 2182 ms 13900 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 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 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 555 ms 7612 KB Output is correct
13 Correct 298 ms 11760 KB Output is correct
14 Correct 942 ms 9344 KB Output is correct
15 Correct 1082 ms 8744 KB Output is correct
16 Correct 728 ms 7764 KB Output is correct
17 Correct 1036 ms 9360 KB Output is correct
18 Correct 941 ms 8796 KB Output is correct
19 Correct 1008 ms 15416 KB Output is correct
20 Correct 2569 ms 9876 KB Output is correct
21 Correct 475 ms 5716 KB Output is correct
22 Correct 2743 ms 10976 KB Output is correct
23 Correct 955 ms 12852 KB Output is correct
24 Correct 1488 ms 10020 KB Output is correct
25 Correct 2525 ms 14404 KB Output is correct
26 Correct 2173 ms 14672 KB Output is correct
27 Correct 2137 ms 14040 KB Output is correct
28 Runtime error 2 ms 600 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 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 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 1 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 567 ms 7464 KB Output is correct
13 Correct 293 ms 11712 KB Output is correct
14 Correct 935 ms 9120 KB Output is correct
15 Correct 1098 ms 8744 KB Output is correct
16 Correct 738 ms 7560 KB Output is correct
17 Correct 1046 ms 8984 KB Output is correct
18 Correct 933 ms 8612 KB Output is correct
19 Correct 1020 ms 15484 KB Output is correct
20 Correct 2634 ms 9984 KB Output is correct
21 Correct 483 ms 5716 KB Output is correct
22 Correct 2760 ms 11492 KB Output is correct
23 Correct 707 ms 13148 KB Output is correct
24 Correct 1478 ms 10072 KB Output is correct
25 Correct 2519 ms 14856 KB Output is correct
26 Correct 2164 ms 14932 KB Output is correct
27 Correct 2145 ms 13928 KB Output is correct
28 Runtime error 2 ms 600 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -