Submission #762407

#	Time	Username	Problem	Language	Result	Execution time	Memory
762407		SanguineChameleon	Game (IOI13_game)	C++17	0 / 100	2 ms	724 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, 1e9 + 20);
	}
};

node_x *root_x = new node_x();

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

void update_y(node_y *cur, int y, long long val) {
	if (cur->lt == cur->rt) {
		cur->val = val;
		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);
		}
		update_y(cur->left, y, val);
	}
	else {
		if (!cur->right) {
			cur->right = new node_y();
			cur->right->init(mt + 1, cur->rt);
		}
		update_y(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) {
	update_y(cur->root_y, y, val);
	if (cur->lt == cur->rt) {
		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);
	}
}

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

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

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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20