Submission #1311562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311562		kustov_vadim_533	Game (IOI13_game)	C++20	0 / 100	2 ms	576 KiB

game

#include <algorithm>
#include <random>
#include "game.h"

using namespace std;
typedef long long ll;

ll gcd(ll x, ll y) {
	while (x > 0) {
		ll r = y % x;
		y = x;
		x = r;
	}
	return y;
}

mt19937 gen;

struct n1d {
	n1d *l, *r;

	int x, y;

	ll g;
	ll vl;

	n1d(int x_, ll vl_) : x(x_), vl(vl_) {
		l = nullptr;
		r = nullptr;
		y = uniform_int_distribution<int>(numeric_limits<int>::min(), numeric_limits<int>::max())(gen);
		g = vl;
	}

	void upd() {
		g = vl;
		if (l) g = gcd(l->g, g);
		if (r) g = gcd(r->g, g);
	}
};

n1d* merge(n1d* a, n1d* b) {
	if (!a) return b;
	if (!b) return a;

	if (a->y > b->y) {
		a->r = merge(a->r, b);
		a->upd();
		return a;
	}
	else {
		b->l = merge(a, b->l);
		b->upd();
		return b;
	}
}

pair<n1d*, n1d*> split(n1d* a, int x) { // <= x | > x
	if (!a) return { nullptr, nullptr };
	if (a->x <= x) {
		pair<n1d*, n1d*> p = split(a->r, x);
		a->r = p.first;
		a->upd();
		return { a, p.second };
	}
	else {
		pair<n1d*, n1d*> p = split(a->l, x);
		a->l = p.second;
		a->upd();
		return {p.first, a};
	}
}

void insert(n1d* &root, int x, ll vl) {
	pair<n1d*, n1d*> p1 = split(root, x - 1);
	pair<n1d*, n1d*> p2 = split(p1.second, x);
	root = merge(p1.first, merge(new n1d(x, vl), p2.second));
}

ll ask(n1d*& root, int l, int r) {
	pair<n1d*, n1d*> p1 = split(root, l - 1);
	pair<n1d*, n1d*> p2 = split(p1.second, r);
	ll res = 0;
	if (p2.first) {
		res = p2.first->g;
	}
	root = merge(p1.first, merge(p2.first, p2.second));
	return res;
}

struct n2d {
	n2d* l, * r;
	int lx, rx;
	
	n1d* tree;

	n2d(int lx_, int rx_) : lx(lx_), rx(rx_) {
		l = nullptr;
		r = nullptr;
		tree = nullptr;
	}
};

void upd(n2d* v, int p, int q, ll k) {
	insert(v->tree, q, k);
	if (v->rx - v->lx == 1) return;
	int m = (v->lx + v->rx) / 2;
	if (p < m) {
		if (!v->l) {
			v->l = new n2d(v->lx, m);
		}
		upd(v->l, p, q, k);
	}
	else {
		if (!v->r) {
			v->r = new n2d(m, v->rx);
		}
		upd(v->r, p, q, k);
	}
}

ll get(n2d* v, int lx, int rx, int ly, int ry) {
	if (!v) return 0ll;
	if (lx >= v->rx || v->lx >= rx) return 0ll;
	if (v->lx >= lx && v->rx <= rx) return ask(v->tree, ly, ry);
	return gcd(get(v->l, lx, rx, ly, ry), get(v->r, lx, rx, ly, ry));
}

n2d* root;

void init(int R, int C) {
	root = new n2d(0, R);
}

void update(int P, int Q, long long K) {
	upd(root, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	return get(root, P, U + 1, Q, V);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20