Submission #954613

#	Time	Username	Problem	Language	Result	Execution time	Memory
954613		islingr	Game (IOI13_game)	C++17	100 / 100	7242 ms	211916 KiB

game

#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;
	unordered_map<int, gcd_treap> t;
 
	segtree() {}
	segtree(int n) : sz{1} {
		while (sz < n) sz *= 2;
	}
 
	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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20