Submission #437366

#	Time	Username	Problem	Language	Result	Execution time	Memory
437366		cmwqfcmwqf	Game (IOI13_game)	C++14	100 / 100	3698 ms	34036 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 ly, ry, 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, y, y, (int)rnd(), y, v, v};
	return cnt;
}
 
void pushup(int node) 
{ 
	tree[node].ly = ls ? tree[ls].ly : tree[node].v;
	tree[node].ry = rs ? tree[rs].ry : tree[node].v;
	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 node, int x, int y)
{
	if(!node || tree[node].ly > y || tree[node].ry < x) return 0;
	if(x <= tree[node].ly && tree[node].ry <= y) return tree[node].g;
	LL ans = 0;
	if(x <= tree[node].v && tree[node].v <= y) ans = tree[node].val;
	ans = gcd2(ans, gcd2(ask(ls, x, y), ask(rs, x, y)));
	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