oj.uz

답안 #32057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
32057 2017-09-23T18:14:34 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 {
	int x, y;
	nodeY *l, *r;
	llong sum;
} treeY[9600000];

struct nodeX {
	nodeX *l, *r;
	nodeY *t;
} treeX[31 * 22000 + 1];

nodeX * root;

nodeY * makeY() {
	static int top = 0;
	return treeY + (top++);
}
int n, m;
nodeX * makeX() {
	static int top = 0;
	treeX[top].t = makeY();
	treeX[top].t->y = m - 1;
	return treeX + (top++);
}

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

int p, q, u, v, 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;
	int md = (now->x + now->y) / 2;
	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

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^
game.cpp: In function 'llong queryY(nodeY*)':
game.cpp:84:6: warning: unused variable 'md' [-Wunused-variable]
  int md = (now->x + now->y) / 2;
      ^

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 -