Submission #855482

#	Time	Username	Problem	Language	Result	Execution time	Memory
855482		SanguineChameleon	Game (IOI13_game)	C++17	100 / 100	6289 ms	67804 KiB

game

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

mt19937 gen(69420);

struct node_y {
	unsigned long long w;
	pair<int, int> pos;
	long long val;
	node_y *lch;
	node_y *rch;
	int sz;
	long long g;

	node_y(pair<int, int> _pos, long long _val): w(gen()), pos(_pos), val(_val), lch(nullptr), rch(nullptr), sz(1), g(val) {};
};

void fix(node_y *u) {
	u->sz = 1;
	u->g = u->val;
	for (auto v: {u->lch, u->rch}) {
		if (v) {
			u->sz += v->sz;
			u->g = __gcd(u->g, v->g);
		}
	}
}

node_y* merge(node_y *lu, node_y *ru) {
	if (!lu) {
		return ru;
	}
	if (!ru) {
		return lu;
	}
	if (lu->w > ru->w) {
		lu->rch = merge(lu->rch, ru);
		fix(lu);
		return lu;
	}
	else {
		ru->lch = merge(lu, ru->lch);
		fix(ru);
		return ru;
	}
}

pair<node_y*, node_y*> split(node_y *u, pair<int, int> pos) {
	if (!u) {
		return {nullptr, nullptr};
	}
	if (u->pos <= pos) {
		auto parts = split(u->rch, pos);
		u->rch = parts.first;
		fix(u);
		return {u, parts.second};
	}
	else {
		auto parts = split(u->lch, pos);
		u->lch = parts.second;
		fix(u);
		return {parts.first, u};
	}
}

void update_y(node_y *&root_y, int x, int y, long long val) {
	node_y *part1, *part2, *part3;
	tie(part1, part2) = split(root_y, {y, x - 1});
	tie(part2, part3) = split(part2, {y, x});
	root_y = merge(merge(part1, new node_y({y, x}, val)), part3);
}

long long get_y(node_y *&root_y, int ly, int ry) {
	node_y *part1, *part2, *part3;
	tie(part1, part2) = split(root_y, {ly, -1});
	tie(part2, part3) = split(part2, {ry + 1, -1});
	long long res = (part2 ? part2->g : 0);
	root_y = merge(merge(part1, part2), part3);
	return res;
}

struct node_x {
	node_y *root_y;
	node_x *lch;
	node_x *rch;

	node_x(): root_y(nullptr), lch(nullptr), rch(nullptr) {};
};

void update_x(node_x *&u, int lt, int rt, int x, int y, long long val) {
	if (!u) {
		u = new node_x();
	}
	update_y(u->root_y, x, y, val);
	if (lt == rt) {
		return;
	}
	int mt = (lt + rt) >> 1;
	if (x <= mt) {
		update_x(u->lch, lt, mt, x, y, val);
	}
	else {
		update_x(u->rch, mt + 1, rt, x, y, val);
	}
};

long long get_x(node_x *u, int lt, int rt, int lx, int rx, int ly, int ry) {
	if (!u) {
		return 0LL;
	}
	if (lt == lx && rt == rx) {
		return get_y(u->root_y, ly, ry);
	}
	int mt = (lt + rt) >> 1;
	if (rx <= mt) {
		return get_x(u->lch, lt, mt, lx, rx, ly, ry);
	}
	else if (lx >= mt + 1) {
		return get_x(u->rch, mt + 1, rt, lx, rx, ly, ry);
	}
	else {
		return __gcd(get_x(u->lch, lt, mt, lx, mt, ly, ry), get_x(u->rch, mt + 1, rt, mt + 1, rx, ly, ry));
	}
}

int n, m;
node_x *root_x = nullptr;

void init(int _n, int _m) {
	n = _n;
	m = _m;
}

void update(int x, int y, long long val) {
	x++;
	y++;
	update_x(root_x, 1, n, x, y, val);
}

long long calculate(int lx, int ly, int rx, int ry) {
	lx++;
	ly++;
	rx++;
	ry++;
	return get_x(root_x, 1, n, lx, rx, ly, ry);
}

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