Submission #417972

#	Time	Username	Problem	Language	Result	Execution time	Memory
417972		Mlxa	Game (IOI13_game)	C++14	100 / 100	7549 ms	39244 KiB

game

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "game.h"

ll gcd(ll x, ll y) {
	ll tmp;
	while (x != y && y != 0) {
		tmp = x;
		x = y;
		y = tmp % y;
	}
	return x;
}

const int TREAP_NODES = 1e6;

mt19937 rnd;

namespace dd {
struct treap {
	int ls, rs, ke, pr;
	ll va, gc;
} pool[TREAP_NODES];
int treap_ff = 1;
#define gt(x,type) type &x(int v) { assert(0 <= v && v < TREAP_NODES); return pool[v].x; }
gt(ls,int) gt(rs,int) gt(ke,int) gt(pr,int) gt(va,ll) gt(gc,ll)
#undef gt

int new_node(int x, ll q) {
	int v = treap_ff++;
	ls(v) = rs(v) = 0;
	ke(v) = x;
	pr(v) = (int)rnd();
	va(v) = gc(v) = q;
	return v;
}

int pull(int v) {
	gc(v) = gcd(va(v), gcd(gc(ls(v)), gc(rs(v))));
	return v;
}

int merge(int l, int r) {
	if (!l) {
		return r;
	}
	if (!r) {
		return l;
	}
	if (pr(l) < pr(r)) {
		rs(l) = merge(rs(l), r);
		return pull(l);
	} else {
		ls(r) = merge(l, ls(r));
		return pull(r);
	}
}

pair<int, int> split(int t, int x) {
	if (!t) {
		return {t, t};
	}
	int l, r;
	if (x < ke(t)) {
		tie(l, ls(t)) = split(ls(t), x);
		r = pull(t);
	} else {
		tie(rs(t), r) = split(rs(t), x);
		l = pull(t);
	}
	return {l, r};
}

ll query(int t, int ql, int qr) {
	int tl, tm, tr;
	tie(tl, tm) = split(t, ql - 1);
	tie(tm, tr) = split(tm, qr - 1);
	ll res = gc(tm);
	int nt = merge(merge(tl, tm), tr);
	assert(t == nt);
	return res;
}

__attribute__((warn_unused_result))
int upd(int t, int pos, ll val) {
	int tl, tm, tr;
	tie(tl, tm) = split(t, pos - 1);
	tie(tm, tr) = split(tm, pos);
	if (tm) {
		assert(!ls(tm) && !rs(tm));
		assert(ke(tm) == pos);
		va(tm) = gc(tm) = val;
	} else {
		tm = new_node(pos, val);
	}
	return merge(merge(tl, tm), tr);
}

void print(int t, int h = 0) {
	if (t) {
		print(ls(t), h + 1);
		cout << ke(t) << ":" << va(t) << " ";
		print(rs(t), h + 1);
	}
	if (!h) {
		cout << endl;
	}
}
}

const int ST_NODES = 1e6;
const int RANGE    = 1e9 + 10;
struct node {
	int ls, rs, tr;
} pool[ST_NODES];
int ff_st = 1;

#define gt(x,type) type &x(int v) { assert(0 <= v && v < ST_NODES); return pool[v].x; }
gt(ls,int) gt(rs,int) gt(tr,int)
#undef gt

int new_node() {
	int v = ff_st++;
	ls(v) = rs(v) = tr(v) = 0;
	return v;
}

ll query(int v, int vl, int vr, int ql, int qr, int yl, int yr) {
	if (!v || qr <= vl || vr <= ql) {
		return 0;
	}
	if (ql <= vl && vr <= qr) {
		return dd::query(tr(v), yl, yr);
	}
	int vm = (vl + vr) / 2;
	return gcd(query(ls(v), vl, vm, ql, qr, yl, yr), query(rs(v), vm, vr, ql, qr, yl, yr));
}

__attribute__((warn_unused_result))
int upd(int v, int vl, int vr, int x, int y, ll to) {
	assert(vl <= x && x < vr);
	if (!v) {
		v = new_node();
	}
	if (vr - vl == 1) {
		tr(v) = dd::upd(tr(v), y, to);
		return v;
	}
	int vm = (vl + vr) / 2;
	if (x < vm) {
		ls(v) = upd(ls(v), vl, vm, x, y, to);
		ll nval = dd::query(tr(rs(v)), y, y + 1);
		nval = gcd(nval, dd::query(tr(ls(v)), y, y + 1));
		nval = gcd(nval, to);
		tr(v) = dd::upd(tr(v), y, nval);
	} else {
		rs(v) = upd(rs(v), vm, vr, x, y, to);
		ll nval = dd::query(tr(ls(v)), y, y + 1);
		nval = gcd(nval, dd::query(tr(rs(v)), y, y + 1));
		nval = gcd(nval, to);
		tr(v) = dd::upd(tr(v), y, nval);
	}
	return v;
}

void init(int r, int c) {
	(void)r; (void)c;
}

int root = 0;

void dfs(int v, int vl, int vr) {
	if (!v) {
		return;
	}
	cout << "#\t" << vl << " " << vr << endl;
	dd::print(tr(v));
	int vm = (vl + vr) / 2;
	dfs(ls(v), vl, vm);
	dfs(rs(v), vm, vr);
}
 
void update(int p, int q, ll k) {
	root = upd(root, 0, RANGE, p, q, k);
	// dfs(root, 0, RANGE);
}
 
ll calculate(int p, int q, int u, int v) {
	return query(root, 0, RANGE, p, u + 1, q, v + 1);
}
 
#ifdef LC
#include "grader.c"
#endif

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