oj.uz

Submission #954602

# Submission time Handle Problem Language Result Execution time Memory
954602 2024-03-28T08:08:16 Z islingr Game (IOI13_game) C++17
10 / 100
 13000 ms 29048 KB 
#include "game.h"

#include "bits/stdc++.h"
using namespace std;

using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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(root, kr);
		const auto g = val(X);
		root = merge(L, merge(X, R));
		return g;
	}
};
*/

struct gcd_treap {
	map<K, ll> mp;

	void set(K k, ll val) { mp[k] = val; }
	ll query(int l, int r) {
		ll g = 0;
		for (auto [k, v] : mp)
			if (l <= k[0] && k[0] < r)
				g = gcd(g, v);
		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(m);
}

void update(int i, int j, ll val) {
	swap(i, j);
	t.set(i, j, val);
}

ll calculate(int l, int u, int r, int d) {
	swap(l, u);
	swap(r, d);

	++r, ++d;
	return t.query(l, r, u, d);
}

Subtask #1
10.0 / 10.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 1 ms 352 KB Output is correct
5 Correct 1 ms 356 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 356 KB Output is correct
8 Correct 0 ms 352 KB Output is correct
9 Correct 0 ms 360 KB Output is correct
10 Correct 0 ms 356 KB Output is correct
11 Correct 0 ms 352 KB Output is correct
12 Correct 0 ms 352 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 0 ms 356 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Execution timed out 13006 ms 28976 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 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 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Execution timed out 13032 ms 13188 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Execution timed out 13088 ms 29048 KB Time limit exceeded
13 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 0 ms 348 KB Output is correct
3 Correct 0 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 1 ms 348 KB Output is correct
8 Correct 1 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 1 ms 348 KB Output is correct
12 Execution timed out 13022 ms 28992 KB Time limit exceeded
13 Halted 0 ms 0 KB -