제출 #855470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855470		SanguineChameleon	게임 (IOI13_game)	C++17	10 / 100	13075 ms	14496 KiB

game

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

struct node_y {
	map<pair<int, int>, long long> vals;
};

node_y* update_y(node_y *u, int x, int y, long long val) {
	if (!u) {
		u = new node_y();
	}
	u->vals[{x, y}] = val;
	return u;
}

long long get_y(node_y *u, int ly, int ry) {
	if (!u) {
		return 0LL;
	}
	long long res = 0;
	for (auto [p, val]: u->vals) {
		if (ly <= p.second && p.second <= ry) {
			res = __gcd(res, val);
		}
	}
	return res;
}

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

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

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

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++;
	root_x = 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: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20