Submission #437319

#	Time	Username	Problem	Language	Result	Execution time	Memory
437319		denverjin	Game (IOI13_game)	C++14	80 / 100	2650 ms	96820 KiB

game

#include "game.h"
#include <bits/stdc++.h>

typedef long long i64;

i64 gcd(i64 X, i64 Y) {
	i64 tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

struct Node {
	int x, lx, rx;
	i64 v, s;
	int sz;
	int ls, rs;
} t[22000 * 30];

const int null = 0;
int ndsz;

int new_node(int x, i64 v) {
	int i = ++ ndsz;
	t[i].x = t[i].lx = t[i].rx = x;
	t[i].v = t[i].s = v;
	t[i].sz = 1;
	t[i].ls = t[i].rs = null;
	return i;
}

void pushup(int x) {
	t[x].sz = t[t[x].ls].sz + 1 + t[t[x].rs].sz;
	t[x].s = gcd(t[t[x].ls].s, gcd(t[x].v, t[t[x].rs].s));
	t[x].lx = t[x].ls ? t[t[x].ls].lx : t[x].x;
	t[x].rx = t[x].rs ? t[t[x].rs].rx : t[x].x;
}

void split(int x, i64 v, int &a, int &b) {
	if (!x) return void(a = b = null);
	if (t[x].x <= v) a = x, split(t[x].rs, v, t[a].rs, b), pushup(a);
	else b = x, split(t[x].ls, v, a, t[b].ls), pushup(b);
}

std::mt19937 rng;

int rand(int l, int r) { return rng() % (r - l + 1) + l; }

int merge(int a, int b) {
	if (!a || !b) return a | b;
	if (rand(1, t[a].sz + t[b].sz) <= t[a].sz) return t[a].rs = merge(t[a].rs, b), pushup(a), a;
	else return t[b].ls = merge(a, t[b].ls), pushup(b), b;
}

void change(int &i, int p, i64 v) {
	int a, b, c;
	split(i, p, b, c);
	split(b, p - 1, a, b);
	if (!b) b = new_node(p, v);
	else t[b].v = t[b].s = v;
	i = merge(merge(a, b), c);
}

i64 query(int i, int l, int r) {
	if (i == null) return 0;
	if (l <= t[i].lx && t[i].rx <= r) return t[i].s;
	if (r < t[i].lx || t[i].rx < l) return 0;
	i64 ans = 0;
	if (l <= t[i].x && t[i].x <= r) ans = gcd(ans, t[i].v);
	if (l < t[i].x && t[i].ls) ans = gcd(ans, query(t[i].ls, l, r));
	if (r > t[i].x && t[i].rs) ans = gcd(ans, query(t[i].rs, l, r));
	return ans;
}

struct SegNode {
	int nd;
	SegNode *ls, *rs;
};

void change(int x, int y, i64 v, SegNode *&i, int a, int b) {
	if (!i) i = new SegNode{0, nullptr, nullptr};
	if (a + 1 == b) return change(i->nd, y, v);
	int m = (a + b) >> 1;
	if (x < m) change(x, y, v, i->ls, a, m);
	else change(x, y, v, i->rs, m, b);
	change(i->nd, y, gcd(i->ls ? query(i->ls->nd, y, y) : 0, i->rs ? query(i->rs->nd, y, y) : 0));
}

i64 query(int l, int r, int L, int R, SegNode *i, int a, int b) {
	if (!i) return 0;
	if (l <= a && b <= r) return query(i->nd, L, R);
	if (r <= a || b <= l) return 0;
	int m = (a + b) >> 1;
	return gcd(query(l, r, L, R, i->ls, a, m), query(l, r, L, R, i->rs, m, b));
}

int R, C;
SegNode *rt;

void init(int _R, int _C) {
	R = _R; C = _C;
	rt = nullptr;
}

void update(int P, int Q, i64 K) {
	change(P, Q, K, rt, 0, R);
}

i64 calculate(int P, int Q, int U, int V) {
	return query(P, U + 1, Q, V, rt, 0, R);
}

#ifdef DEBUG
#include "grader.c"
#endif

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