답안 #32062 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32062	2017-09-23T18:46:08 Z	imeimi2000	게임 (IOI13_game)	C++14	100 / 100	6666 ms	76412 KB

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

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

#	결과	메모리	Grader output
1	Correct	1172 KB	Output is correct
2	Correct	1304 KB	Output is correct
3	Correct	1304 KB	Output is correct
4	Correct	1172 KB	Output is correct
5	Correct	1172 KB	Output is correct
6	Correct	1304 KB	Output is correct
7	Correct	1172 KB	Output is correct
8	Correct	1172 KB	Output is correct
9	Correct	1304 KB	Output is correct
10	Correct	1172 KB	Output is correct
11	Correct	1172 KB	Output is correct
12	Correct	1172 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1172 KB	Output is correct
2	Correct	0 ms	1172 KB	Output is correct
3	Correct	0 ms	1172 KB	Output is correct
4	Correct	779 ms	5132 KB	Output is correct
5	Correct	486 ms	5132 KB	Output is correct
6	Correct	769 ms	5264 KB	Output is correct
7	Correct	929 ms	5264 KB	Output is correct
8	Correct	593 ms	3152 KB	Output is correct
9	Correct	863 ms	5264 KB	Output is correct
10	Correct	826 ms	5264 KB	Output is correct
11	Correct	0 ms	1172 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1172 KB	Output is correct
2	Correct	0 ms	1304 KB	Output is correct
3	Correct	0 ms	1304 KB	Output is correct
4	Correct	0 ms	1172 KB	Output is correct
5	Correct	0 ms	1172 KB	Output is correct
6	Correct	0 ms	1304 KB	Output is correct
7	Correct	0 ms	1172 KB	Output is correct
8	Correct	0 ms	1172 KB	Output is correct
9	Correct	0 ms	1304 KB	Output is correct
10	Correct	0 ms	1172 KB	Output is correct
11	Correct	0 ms	1172 KB	Output is correct
12	Correct	1283 ms	8300 KB	Output is correct
13	Correct	3176 ms	5132 KB	Output is correct
14	Correct	363 ms	1304 KB	Output is correct
15	Correct	3416 ms	6320 KB	Output is correct
16	Correct	319 ms	10148 KB	Output is correct
17	Correct	1386 ms	5792 KB	Output is correct
18	Correct	2919 ms	10148 KB	Output is correct
19	Correct	2223 ms	10148 KB	Output is correct
20	Correct	2099 ms	10148 KB	Output is correct
21	Correct	0 ms	1172 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1172 KB	Output is correct
2	Correct	0 ms	1304 KB	Output is correct
3	Correct	0 ms	1304 KB	Output is correct
4	Correct	0 ms	1172 KB	Output is correct
5	Correct	0 ms	1172 KB	Output is correct
6	Correct	0 ms	1304 KB	Output is correct
7	Correct	0 ms	1172 KB	Output is correct
8	Correct	0 ms	1172 KB	Output is correct
9	Correct	0 ms	1304 KB	Output is correct
10	Correct	0 ms	1172 KB	Output is correct
11	Correct	0 ms	1172 KB	Output is correct
12	Correct	819 ms	5132 KB	Output is correct
13	Correct	489 ms	5132 KB	Output is correct
14	Correct	826 ms	5264 KB	Output is correct
15	Correct	1018 ms	5264 KB	Output is correct
16	Correct	579 ms	3152 KB	Output is correct
17	Correct	839 ms	5264 KB	Output is correct
18	Correct	703 ms	5264 KB	Output is correct
19	Correct	1166 ms	8300 KB	Output is correct
20	Correct	3079 ms	5132 KB	Output is correct
21	Correct	379 ms	1304 KB	Output is correct
22	Correct	3379 ms	6320 KB	Output is correct
23	Correct	303 ms	10148 KB	Output is correct
24	Correct	1219 ms	5792 KB	Output is correct
25	Correct	2473 ms	10148 KB	Output is correct
26	Correct	2179 ms	10148 KB	Output is correct
27	Correct	2546 ms	10148 KB	Output is correct
28	Correct	829 ms	35756 KB	Output is correct
29	Correct	2079 ms	35228 KB	Output is correct
30	Correct	5006 ms	30080 KB	Output is correct
31	Correct	4536 ms	22820 KB	Output is correct
32	Correct	619 ms	1436 KB	Output is correct
33	Correct	843 ms	1964 KB	Output is correct
34	Correct	476 ms	35228 KB	Output is correct
35	Correct	1996 ms	18200 KB	Output is correct
36	Correct	4459 ms	35228 KB	Output is correct
37	Correct	3479 ms	35228 KB	Output is correct
38	Correct	3363 ms	35228 KB	Output is correct
39	Correct	2686 ms	27176 KB	Output is correct
40	Correct	0 ms	1172 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1172 KB	Output is correct
2	Correct	0 ms	1304 KB	Output is correct
3	Correct	0 ms	1304 KB	Output is correct
4	Correct	0 ms	1172 KB	Output is correct
5	Correct	0 ms	1172 KB	Output is correct
6	Correct	0 ms	1304 KB	Output is correct
7	Correct	0 ms	1172 KB	Output is correct
8	Correct	0 ms	1172 KB	Output is correct
9	Correct	0 ms	1304 KB	Output is correct
10	Correct	0 ms	1172 KB	Output is correct
11	Correct	0 ms	1172 KB	Output is correct
12	Correct	849 ms	5132 KB	Output is correct
13	Correct	553 ms	5132 KB	Output is correct
14	Correct	866 ms	5264 KB	Output is correct
15	Correct	923 ms	5264 KB	Output is correct
16	Correct	566 ms	3152 KB	Output is correct
17	Correct	956 ms	5264 KB	Output is correct
18	Correct	849 ms	5264 KB	Output is correct
19	Correct	1263 ms	8300 KB	Output is correct
20	Correct	3056 ms	5132 KB	Output is correct
21	Correct	379 ms	1304 KB	Output is correct
22	Correct	3373 ms	6320 KB	Output is correct
23	Correct	296 ms	10148 KB	Output is correct
24	Correct	1256 ms	5792 KB	Output is correct
25	Correct	2469 ms	10148 KB	Output is correct
26	Correct	1913 ms	10148 KB	Output is correct
27	Correct	2256 ms	10148 KB	Output is correct
28	Correct	806 ms	35756 KB	Output is correct
29	Correct	2043 ms	35228 KB	Output is correct
30	Correct	4573 ms	30080 KB	Output is correct
31	Correct	4119 ms	22820 KB	Output is correct
32	Correct	563 ms	1436 KB	Output is correct
33	Correct	779 ms	1964 KB	Output is correct
34	Correct	389 ms	35228 KB	Output is correct
35	Correct	1673 ms	18200 KB	Output is correct
36	Correct	3783 ms	35228 KB	Output is correct
37	Correct	2936 ms	35228 KB	Output is correct
38	Correct	2689 ms	35228 KB	Output is correct
39	Correct	989 ms	76412 KB	Output is correct
40	Correct	3546 ms	75356 KB	Output is correct
41	Correct	6666 ms	63212 KB	Output is correct
42	Correct	6196 ms	47768 KB	Output is correct
43	Correct	929 ms	75356 KB	Output is correct
44	Correct	699 ms	1568 KB	Output is correct
45	Correct	2133 ms	27176 KB	Output is correct
46	Correct	4889 ms	75356 KB	Output is correct
47	Correct	5169 ms	75356 KB	Output is correct
48	Correct	4833 ms	75356 KB	Output is correct
49	Correct	0 ms	1172 KB	Output is correct

답안 #32062

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 20.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
20.0 / 20.0