Submission #762459

#	Time	Username	Problem	Language	Result	Execution time	Memory
762459		SanguineChameleon	Game (IOI13_game)	C++17	80 / 100	3703 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;
	int left = 0;
	int right = 0;

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

const int max_nodes = 1e7 + 20;
int node_x_cnt = 0;
int node_y_cnt = 0;
int R, C;

node_y nodes_y[max_nodes];

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

	void init(int _lt, int _rt) {
		lt = _lt;
		rt = _rt;
		root_y = ++node_y_cnt;
		nodes_y[root_y].init(0, (1 << 30) - 1);
	}
};

node_x nodes_x[max_nodes];

int root_x = ++node_x_cnt;

void init(int _R, int _C) {
	R = _R;
	C = _C;
	nodes_x[root_x].init(0, R - 1);
}

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

void update_y(int par, int cur, int y, long long val) {
	if (nodes_y[cur].lt == nodes_y[cur].rt) {
		if (nodes_x[par].lt == nodes_x[par].rt) {
			nodes_y[cur].val = val;
		}
		else {
			nodes_y[cur].val = __gcd(nodes_x[par].left ? get_y(nodes_x[nodes_x[par].left].root_y, y, y) : 0LL, nodes_x[par].right ? get_y(nodes_x[nodes_x[par].right].root_y, y, y) : 0LL);
		}
		return;
	}
	int mt = (nodes_y[cur].lt + nodes_y[cur].rt) / 2;
	if (y <= mt) {
		if (!nodes_y[cur].left) {
			nodes_y[cur].left = ++node_y_cnt;
			nodes_y[nodes_y[cur].left].init(nodes_y[cur].lt, mt);
		}
		int lt = nodes_y[nodes_y[cur].left].lt;
		int rt = nodes_y[nodes_y[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) {
			int mid = ++node_y_cnt;
			nodes_y[mid].init(lt, rt);
			nodes_y[mid].left = nodes_y[cur].left;
			nodes_y[cur].left = mid;
		}
		if (prv == 1) {
			int mid = ++node_y_cnt;
			nodes_y[mid].init(lt, rt);
			nodes_y[mid].right = nodes_y[cur].left;
			nodes_y[cur].left = mid;
		}
		update_y(par, nodes_y[cur].left, y, val);
	}
	else {
		if (!nodes_y[cur].right) {
			nodes_y[cur].right = ++node_y_cnt;
			nodes_y[nodes_y[cur].right].init(mt + 1, nodes_y[cur].rt);
		}
		int lt = nodes_y[nodes_y[cur].right].lt;
		int rt = nodes_y[nodes_y[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) {
			int mid = ++node_y_cnt;
			nodes_y[mid].init(lt, rt);
			nodes_y[mid].left = nodes_y[cur].right;
			nodes_y[cur].right = mid;
		}
		if (prv == 1) {
			int mid = ++node_y_cnt;
			nodes_y[mid].init(lt, rt);
			nodes_y[mid].right = nodes_y[cur].right;
			nodes_y[cur].right = mid;
		}
		update_y(par, nodes_y[cur].right, y, val);
	}
	nodes_y[cur].val = __gcd(nodes_y[cur].left ? nodes_y[nodes_y[cur].left].val : 0LL, nodes_y[cur].right ? nodes_y[nodes_y[cur].right].val : 0LL);
}

void update_x(int cur, int x, int y, long long val) {
	if (nodes_x[cur].lt == nodes_x[cur].rt) {
		update_y(cur, nodes_x[cur].root_y, y, val);
		return;
	}
	int mt = (nodes_x[cur].lt + nodes_x[cur].rt) / 2;
	if (x <= mt) {
		if (!nodes_x[cur].left) {
			nodes_x[cur].left = ++node_x_cnt;
			nodes_x[nodes_x[cur].left].init(nodes_x[cur].lt, mt);
		}
		update_x(nodes_x[cur].left, x, y, val);
	}
	else {
		if (!nodes_x[cur].right) {
			nodes_x[cur].right = ++node_x_cnt;
			nodes_x[nodes_x[cur].right].init(mt + 1, nodes_x[cur].rt);
		}
		update_x(nodes_x[cur].right, x, y, val);
	}
	update_y(cur, nodes_x[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(int cur, int lx, int rx, int ly, int ry) {
	if (!cur) {
		return 0LL;
	}
	if (nodes_x[cur].rt < lx || nodes_x[cur].lt > rx) {
		return 0LL;
	}
	if (lx <= nodes_x[cur].lt && nodes_x[cur].rt <= rx) {
		return get_y(nodes_x[cur].root_y, ly, ry);
	}
	return __gcd(get_x(nodes_x[cur].left, lx, rx, ly, ry), get_x(nodes_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: 17 / 17
• Subtask 5: 0 / 20