제출 #650753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650753		ymm	Game (IOI13_game)	C++17	80 / 100	3590 ms	256000 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;
	node0 *l, *r;
} pool0[10000000];
struct node1 {
	node0 x;
	node1 *l, *r;
} pool1[10000000];
node0 *new_node0(){static int nxt=0; return &pool0[nxt++];}
node1 *new_node1(){static int nxt=0; return &pool1[nxt++];}

void up0(int p, ll x, node0 *t, int b=0, int e=1e9)
{
	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? t->l->x: 0, t->r? t->r->x: 0);
}

void merge0(int p, node0 *l, node0 *r, node0 *t, int b=0, int e=1e9)
{
	t->x = __gcd(l? l->x: 0, r? r->x: 0);
	if (e-b == 1)
		return;
	if (p < (b+e)/2) {
		if (!t->l) t->l = new_node0();
		merge0(p, l? l->l: NULL, r? r->l: NULL, t->l, b, (b+e)/2);
	} else {
		if (!t->r) t->r = new_node0();
		merge0(p, l? l->r: NULL, r? r->r: NULL, t->r, (b+e)/2, e);
	}
}

ll get0(int l, int r, node0 *t, int b=0, int e=1e9)
{
	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));
}

void up1(int p1, int p0, ll x, node1 *t, int b=0, int e=1e9)
{
	if (e-b == 1) {
		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);
	}
	merge0(p0, t->l? &t->l->x: NULL, t->r? &t->r->x: NULL, &t->x);
}

ll get1(int l1, int r1, int l0, int r0, node1 *t, int b=0, int e=1e9)
{
	if (r1 <= b || e <= l1 || !t)
		return 0;
	if (l1 <= b && e <= r1)
		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));
}

node1 *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: 0 / 20