Submission #32062

#	Time	Username	Problem	Language	Result	Execution time	Memory
32062		imeimi2000	Game (IOI13_game)	C++14	100 / 100	6666 ms	76412 KiB

game

#include "game.h"

using namespace std;
typedef long long llong;

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

struct nodeY {
	int x, y;
	nodeY *l, *r;
	llong sum;
};

struct nodeX {
	nodeX *l, *r;
	nodeY *t;
};

nodeX * root;

nodeY * makeY() {
	//static int top = 0;
	nodeY * ret = new nodeY;
	ret->l = ret->r = 0;
	ret->sum = 0;
	return ret;
}
int n, m;
nodeX * makeX() {
	//static int top = 0;
	nodeX * ret = new nodeX;
	ret->t = makeY();
	ret->l = ret->r = 0;
	ret->t->x = 0;
	ret->t->y = m - 1;
	return ret;
}

void init(int r, int c) {
	n = r; m = c;
	root = makeX();
}

int p, q, u, v;
llong k, uk;
void updtY(nodeY * now) {
	if (now->x == now->y) {
		now->sum = uk;
		return;
	}

	int md = (now->x + now->y) / 2;
	nodeY *& nxt = q <= md ? now->l : now->r;
	if (nxt == 0) {
		nxt = makeY();
		nxt->x = nxt->y = q;
		nxt->sum = uk;
	}
	else if (nxt->x <= q && q <= nxt->y) {
		updtY(nxt);
	}
	else {
		nodeY * nw = makeY();
		nw->x = now->x;
		nw->y = now->y;
		do {
			if (q <= md) nw->y = md;
			else nw->x = md + 1;
			md = (nw->x + nw->y) / 2;
		} while ((q <= md) == (nxt->x <= md));
		if (q <= md) nw->r = nxt;
		else nw->l = nxt;
		nxt = nw;
		updtY(nw);
	}
	now->sum = gcd2(now->l ? now->l->sum : 0ll, now->r ? now->r->sum : 0ll);
}

llong queryY(nodeY * now) {
	if (now == 0) return 0ll;
	if (v < now->x || now->y < q) return 0ll;
	if (q <= now->x && now->y <= v) return now->sum;
	return gcd2(queryY(now->l), queryY(now->r));
}

void updtX(nodeX * now, int x, int y) {
	if (x == y) {
		uk = k;
		updtY(now->t);
		return;
	}
	int md = (x + y) / 2;
	if (p <= md) {
		if (now->l == 0) now->l = makeX();
		updtX(now->l, x, md);
	}
	else {
		if (now->r == 0) now->r = makeX();
		updtX(now->r, md + 1, y);
	}
	uk = gcd2(now->l ? queryY(now->l->t) : 0ll, now->r ? queryY(now->r->t) : 0ll);
	updtY(now->t);
}

llong queryX(nodeX * now, int x, int y) {
	if (now == 0) return 0ll;
	if (u < x || y < p) return 0ll;
	if (p <= x && y <= u) return queryY(now->t);
	int md = (x + y) / 2;
	return gcd2(queryX(now->l, x, md), queryX(now->r, md + 1, y));
}

void update(int P, int Q, llong K) {
	p = u = P;
	q = v = Q;
	k = K;
	updtX(root, 0, n - 1);
}

long long calculate(int P, int Q, int U, int V) {
	p = P; q = Q; u = U; v = V;
    return queryX(root, 0, n - 1);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

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