Submission #762447

#	Time	Username	Problem	Language	Result	Execution time	Memory
762447		SanguineChameleon	Game (IOI13_game)	C++17	63 / 100	1911 ms	256000 KiB

game

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

struct node_y {
	int lt = 0;
	int rt = 0;
	long long val = 0;
	node_y *left = nullptr;
	node_y *right = nullptr;

	void init(int _lt, int _rt) {
		lt = _lt;
		rt = _rt;
	}
};

int R, C;

struct node_x {
	int lt = 0;
	int rt = 0;
	node_y *root_y = nullptr;
	node_x *left = nullptr;
	node_x *right = nullptr;

	void init(int _lt, int _rt) {
		lt = _lt;
		rt = _rt;
		root_y = new node_y();
		root_y->init(0, (1 << 30) - 1);
	}
};

node_x *root_x = new node_x();

void init(int _R, int _C) {
	R = _R;
	C = _C;
	root_x->init(0, R - 1);
}

long long get_y(node_y *cur, int ly, int ry) {
	if (!cur) {
		return 0LL;
	}
	if (cur->rt < ly || cur->lt > ry) {
		return 0LL;
	}
	if (ly <= cur->lt && cur->rt <= ry) {
		return cur->val;
	}
	return __gcd(get_y(cur->left, ly, ry), get_y(cur->right, ly, ry));
}

void update_y(node_x *par, node_y *cur, int y, long long val) {
	if (cur->lt == cur->rt) {
		if (par->lt == par->rt) {
			cur->val = val;
		}
		else {
			cur->val = __gcd(par->left ? get_y(par->left->root_y, y, y) : 0LL, par->right ? get_y(par->right->root_y, y, y) : 0LL);
		}
		return;
	}
	int mt = (cur->lt + cur->rt) / 2;
	if (y <= mt) {
		if (!cur->left) {
			cur->left = new node_y();
			cur->left->init(cur->lt, mt);
		}
		int lt = cur->left->lt;
		int rt = cur->left->rt;
		int prv = -1;
		while (y < lt || y > rt) {
			int len = (rt - lt + 1);
			if (lt & rt & len) {
				prv = 1;
				lt -= len;
			}
			else {
				prv = 0;
				rt += len;
			}
		}
		if (prv == 0) {
			node_y *mid = new node_y();
			mid->init(lt, rt);
			mid->left = cur->left;
			cur->left = mid;
		}
		if (prv == 1) {
			node_y *mid = new node_y();
			mid->init(lt, rt);
			mid->right = cur->left;
			cur->left = mid;
		}
		update_y(par, cur->left, y, val);
	}
	else {
		if (!cur->right) {
			cur->right = new node_y();
			cur->right->init(mt + 1, cur->rt);
		}
		int lt = cur->right->lt;
		int rt = cur->right->rt;
		int prv = -1;
		while (y < lt || y > rt) {
			int len = (rt - lt + 1);
			if (lt & rt & len) {
				prv = 1;
				lt -= len;
			}
			else {
				prv = 0;
				rt += len;
			}
		}
		if (prv == 0) {
			node_y *mid = new node_y();
			mid->init(lt, rt);
			mid->left = cur->right;
			cur->right = mid;
		}
		if (prv == 1) {
			node_y *mid = new node_y();
			mid->init(lt, rt);
			mid->right = cur->right;
			cur->right = mid;
		}
		update_y(par, cur->right, y, val);
	}
	cur->val = __gcd(cur->left ? cur->left->val : 0LL, cur->right ? cur->right->val : 0LL);
}

void update_x(node_x *cur, int x, int y, long long val) {
	if (cur->lt == cur->rt) {
		update_y(cur, cur->root_y, y, val);
		return;
	}
	int mt = (cur->lt + cur->rt) / 2;
	if (x <= mt) {
		if (!cur->left) {
			cur->left = new node_x();
			cur->left->init(cur->lt, mt);
		}
		update_x(cur->left, x, y, val);
	}
	else {
		if (!cur->right) {
			cur->right = new node_x();
			cur->right->init(mt + 1, cur->rt);
		}
		update_x(cur->right, x, y, val);
	}
	update_y(cur, cur->root_y, y, val);
}

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

long long get_x(node_x *cur, int lx, int rx, int ly, int ry) {
	if (!cur) {
		return 0LL;
	}
	if (cur->rt < lx || cur->lt > rx) {
		return 0LL;
	}
	if (lx <= cur->lt && cur->rt <= rx) {
		return get_y(cur->root_y, ly, ry);
	}
	return __gcd(get_x(cur->left, lx, rx, ly, ry), get_x(cur->right, lx, rx, ly, ry));
}

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

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