oj.uz

답안 #32056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
32056 2017-09-23T17:34:08 Z imeimi2000 게임 (IOI13_game) C++14
0 / 100
 0 ms 952 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -