Submission #437305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
437305	2021-06-26T07:04:27 Z	denverjin	Game (IOI13_game)	C++14	Compilation error	0 ms	0 KB

game

#ifdef DEBUG
#include "game.h"
#endif
#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;
	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 = 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));
}

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;
	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);
}

Compilation message

/usr/bin/ld: /tmp/ccGtXm30.o: in function `main':
grader.c:(.text.startup+0x6b): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xd0): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status