제출 #954607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954607		islingr	게임 (IOI13_game)	C++17	10 / 100	13066 ms	17780 KiB

game

#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));
	}

	template <class F>
	void for_each(Node* n, F f) {
		if (n) {
			for_each(n->l, f);
			f(n);
			for_each(n->r, f);
		}
	}

	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;
		*/

		ll g = 0;
		for_each(root, [&](Node* n) {
			const auto x = n->key[0];
			if (l <= x && x < r)
				g = gcd(g, n->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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20