제출 #650762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650762		ymm	게임 (IOI13_game)	C++17	100 / 100	4755 ms	147624 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

struct node0 {
	ll x;
	int l, r;
} pool0[10000000];
struct node1 {
	int x;
	int l, r;
} pool1[10000000];
int new_node0(){static int nxt=1; return nxt++;}
int new_node1(){static int nxt=1; return nxt++;}

void up0(int p, ll x, int t, int b=0, int e=1e9)
{
#define t (pool0+t)
	if (e-b == 1) {
		t->x = x;
		return;
	}
	if (p < (b+e)/2) {
		if (!t->l) t->l = new_node0();
		up0(p, x, t->l, b, (b+e)/2);
	} else {
		if (!t->r) t->r = new_node0();
		up0(p, x, t->r, (b+e)/2, e);
	}
	t->x = __gcd(t->l? pool0[t->l].x: 0, t->r? pool0[t->r].x: 0);
#undef t
}

void merge0(int p, int l, int r, int t, int b=0, int e=1e9)
{
#define t (pool0+t)
	t->x = __gcd(l? pool0[l].x: 0, r? pool0[r].x: 0);
	if (e-b == 1)
		return;
	if (p < (b+e)/2) {
		if (!t->l) t->l = new_node0();
		merge0(p, l? pool0[l].l: 0, r? pool0[r].l: 0, t->l, b, (b+e)/2);
	} else {
		if (!t->r) t->r = new_node0();
		merge0(p, l? pool0[l].r: 0, r? pool0[r].r: 0, t->r, (b+e)/2, e);
	}
#undef t
}

ll get0(int l, int r, int t, int b=0, int e=1e9)
{
#define t (pool0+t)
	if (r <= b || e <= l || !t)
		return 0;
	if (l <= b && e <= r)
		return t->x;
	return __gcd(get0(l, r, t->l, b, (b+e)/2),
	             get0(l, r, t->r, (b+e)/2, e));
#undef t
}

int seg0_cpy(int t)
{
	if (!t)
		return 0;
#define t (pool0+t)
	int ans = new_node0();
	pool0[ans].x = t->x;
	pool0[ans].l = seg0_cpy(t->l);
	pool0[ans].r = seg0_cpy(t->r);
	return ans;
#undef t
}

void up1(int p1, int p0, ll x, int t, int b=0, int e=1e9)
{
#define t (pool1+t)
	if (e-b == 1) {
		if (!t->x) t->x = new_node0();
		up0(p0, x, t->x);
		return;
	}
	if (p1 < (b+e)/2) {
		if (!t->l) t->l = new_node1();
		up1(p1, p0, x, t->l, b, (b+e)/2);
	} else {
		if (!t->r) t->r = new_node1();
		up1(p1, p0, x, t->r, (b+e)/2, e);
	}
	if (t->l && t->r) {
		if (!t->x) {
			int u = p1 < (b+e)/2? t->r: t->l;
			while (!pool1[u].x)
				u = pool1[u].l? pool1[u].l: pool1[u].r;
			t->x = seg0_cpy(pool1[u].x);
		}
		int ul = t->l, ur = t->r;
		while (!pool1[ul].x)
			ul = pool1[ul].l? pool1[ul].l: pool1[ul].r;
		while (!pool1[ur].x)
			ur = pool1[ur].l? pool1[ur].l: pool1[ur].r;
		merge0(p0, pool1[ul].x, pool1[ur].x, t->x);
	}
#undef t
}

ll get1(int l1, int r1, int l0, int r0, int t, int b=0, int e=1e9)
{
	if (r1 <= b || e <= l1 || !t)
		return 0;
#define t (pool1+t)
	if (l1 <= b && e <= r1) {
		if (!t->x) {
			if (t->l)
				return get1(l1,r1,l0,r0, t->l, b, (b+e)/2);
			else
				return get1(l1,r1,l0,r0, t->r, (b+e)/2, e);
		} else {
			return get0(l0, r0, t->x);
		}
	}
	return __gcd(get1(l1, r1, l0, r0, t->l, b, (b+e)/2),
	             get1(l1, r1, l0, r0, t->r, (b+e)/2, e));
#undef t
}

int rt = new_node1();

void init(int R, int C)
{
}

void update(int P, int Q, long long K)
{
	up1(P, Q, K, rt);
}

long long calculate(int P, int Q, int U, int V)
{
	int l1 = min(P, U);
	int r1 = max(P, U) + 1;
	int l0 = min(Q, V);
	int r0 = max(Q, V) + 1;
	return get1(l1, r1, l0, r0, rt);
}

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