Submission #32056

#	Time	Username	Problem	Language	Result	Execution time	Memory
32056		imeimi2000	Game (IOI13_game)	C++14	0 / 100	0 ms	952 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 {
	nodeY *l, *r;
	llong sum;
} treeY[30 * 30 * 30000];

struct nodeX {
	nodeX *l, *r;
	nodeY *t;
} treeX[30 * 30000];

nodeX * root;

nodeY * makeY() {
	static int top = 0;
	return treeY + (top++);
}

nodeX * makeX() {
	static int top = 0;
	treeX[top].t = makeY();
	return treeX + (top++);
}

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

int p, q, u, v, k, uk;
void updtY(nodeY * now, nodeY * pre, int x, int y) {
	if (x == y) {
		now->sum = uk;
		return;
	}
	int md = (x + y) / 2;
	if (q <= md) {
		now->l = makeY();
		now->r = pre->r;
		updtY(now->l, pre->l, x, md);
	}
	else {
		now->l = pre->l;
		now->r = makeY();
		updtY(now->r, pre->r, md + 1, y);
	}
	now->sum = gcd2(now->l->sum, now->r->sum);
}

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

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

llong queryX(nodeX * now, int x, int y) {
	if (u < x || y < p) return 0ll;
	if (p <= x && y <= u) return queryY(now->t, 0, m - 1);
	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;
	nodeX * pre = root;
	root = makeX();
	updtX(root, pre, 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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20