Submission #437345

#	Time	Username	Problem	Language	Result	Execution time	Memory
437345		cmwqfcmwqf	Game (IOI13_game)	C++14	100 / 100	7411 ms	28532 KiB

game

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

mt19937 rnd( time(NULL) );

#define LL long long
#define ls tree[node].l
#define rs tree[node].r

const int maxN = 2.2e4 + 10;

struct Treap
{
	int l, r;
	int key, v;
	LL val, g;
}tree[maxN * 35 + 1];

struct Seg
{
	int l, r;
	int rt;
}T[maxN * 35 + 1];

int rt, cnt, ct, R, C;

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

int new_Node(int y, LL v)
{
	tree[++ cnt] = (Treap){0, 0, (int)rnd(), y, v, v};
	return cnt;
}

void pushup(int node) { tree[node].g = gcd2(tree[ls].g, gcd2(tree[node].val, tree[rs].g)); }

void split(int node, int k, int &u, int &v)
{
	if(!node) { u = v = 0; return; }
	if(tree[node].v <= k) u = node, split(rs, k, tree[u].r, v);
	else v = node, split(ls, k, u, tree[v].l);
	pushup(node);
}

int merge(int u, int v)
{
	if(!u || !v) return u | v;
	if(tree[u].key < tree[v].key)
	{
		tree[u].r = merge(tree[u].r, v);
		return pushup(u), u;
	}
	else
	{
		tree[v].l = merge(u, tree[v].l);
		return pushup(v), v;
	}
}

void modify(int &rt, int k, LL val)
{
	int u, v, w;
	split(rt, k, u, v);
	split(u, k - 1, u, w);
	if(!w) w = new_Node(k, val);
	else tree[w].val = tree[w].g = val;
	rt = merge(merge(u, w), v);
}

LL ask(int &rt, int x, int y)
{
	if(!rt) return 0;
	int u, v, w;
	split(rt, y, u, v);
	split(u, x - 1, u, w);
	LL ans = w ? tree[w].g : 0;
	rt = merge(merge(u, w), v);
	return ans;
}

void change(int &node, int l, int r, int x, int y, LL v)
{
	if(!node) node = ++ ct;
	if(l == r) { modify(T[node].rt, y, v); return; }
	int mid = (l + r) >> 1;
	if(x <= mid) change(T[node].l, l, mid, x, y, v);
	else change(T[node].r, mid + 1, r, x, y, v);
	modify(T[node].rt, y, gcd2(ask(T[ T[node].l ].rt, y, y), ask(T[ T[node].r ].rt, y, y)));
}

LL query(int node, int l, int r, int x, int y, int xb, int yb)
{
	if(!node) return 0;
	if(x <= l && r <= y) return ask(T[node].rt, xb, yb);
	int mid = (l + r) >> 1; LL ans = 0;
	if(x <= mid) ans = gcd2(ans, query(T[node].l, l, mid, x, y, xb, yb));
	if(y > mid) ans = gcd2(ans, query(T[node].r, mid + 1, r, x, y, xb, yb));
	return ans;
}

void update(int x, int y, LL v)
{
	change(rt, 0, R - 1, x, y, v);
}

LL calculate(int xa, int ya, int xb, int yb)
{
	return query(rt, 0, R - 1, xa, xb, ya, yb);
}

void init(int r, int c)
{
	R = r; C = c;
}

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