답안 #97698 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97698	2019-02-17T18:11:36 Z	tincamatei	게임 (IOI13_game)	C++14	63 / 100	3229 ms	138296 KB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

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;
}

int R, C;
long long **aint;

int best;

void initxd(int l, int r, int nod = 1) {
	if(nod > best)
		best = nod;
	if(l < r) {
		int mid = (l + r) / 2;
		initxd(l, mid, 2 * nod);
		initxd(mid + 1, r, 2 * nod + 1);
	}
}

void updateSmall(int anod, int poz, long long val, int l, int r, int nod = 1) {
	if(poz < l || r < poz) return;
	if(l == r)
		aint[anod][nod] = val;
	else if(l < r) {
		int mid = (l + r) / 2;
		updateSmall(anod, poz, val, l, mid, 2 * nod);
		updateSmall(anod, poz, val, mid + 1, r, 2 * nod + 1);
		aint[anod][nod] = gcd2(aint[anod][2 * nod], aint[anod][2 * nod + 1]);
	}
}

long long querySmall(int anod, int i, int j, int l, int r, int nod = 1) {
	if(r < i || j < l) return 0;
	if(i <= l && r <= j)
		return aint[anod][nod];
	else if(l < r) {
		int mid = (l + r) / 2;
		return gcd2(querySmall(anod, i, j, l, mid, 2 * nod),
		            querySmall(anod, i, j, mid + 1, r, 2 * nod + 1));
	}
	return 0;
}

void updateBig(int i, int j, long long val, int l, int r, int nod = 1) {
	if(i < l || r < i) return;
	if(l == r)
		updateSmall(nod, j, val, 0, C - 1);
	if(l < r) {
		int mid = (l + r) / 2;
		updateBig(i, j, val, l, mid, 2 * nod);
		updateBig(i, j, val, mid + 1, r, 2 * nod + 1);
		long long x = gcd2(querySmall(2 * nod,     j, j, 0, C - 1),
		                   querySmall(2 * nod + 1, j, j, 0, C - 1));
		updateSmall(nod, j, x, 0, C - 1);
	}
}

long long queryBig(int p, int q, int u, int v, int l, int r, int nod = 1) {
	if(r < p || q < l || p > q) return 0;
	if(p <= l && r <= q)
		return querySmall(nod, u, v, 0, C - 1);
	else if(l < r) {
		int mid = (l + r) / 2;
		return gcd2(queryBig(p, q, u, v, l, mid, 2 * nod),
		            queryBig(p, q, u, v, mid + 1, r, 2 * nod + 1));
	}
	return 0;
}

void init(int _R, int _C) {
	R = _R;
	C = _C;
	int allR, allC;
	allR = 1 + 4 * _R;
	allC = 1 + 4 * _C;
	aint = new long long*[allR];
	if(R > 100) // subtask 3
		allR = allC = 4094;
	for(int i = 0; i < allR; ++i) {
		aint[i] = new long long[allC];
		for(int j = 0; j < allC; ++j)
			aint[i][j] = 0LL;
	}
}

void update(int P, int Q, long long K) {
	updateBig(P, Q, K, 0, R - 1);
	//updateSmall(P, Q, K, 0, C - 1);
	//aint[P][Q] = K;
}

long long calculate(int P, int Q, int U, int V) {
	//long long rez = 0LL;
	//for(int i = P; i <= U; ++i)
	//	for(int j = Q; j <= V; ++j)
	//		rez = gcd2(aint[i][j], rez);
	//long long rez = 0LL;
	//for(int i = P; i <= U; ++i)
	//	rez = gcd2(rez, querySmall(i, Q, V, 0, C - 1));
	return queryBig(P, U, Q, V, 0, R - 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	3 ms	256 KB	Output is correct
2	Correct	5 ms	1664 KB	Output is correct
3	Correct	4 ms	1664 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	3 ms	1664 KB	Output is correct
6	Correct	4 ms	1664 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	4 ms	1536 KB	Output is correct
10	Correct	4 ms	1664 KB	Output is correct
11	Correct	4 ms	1664 KB	Output is correct
12	Correct	2 ms	256 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	356 KB	Output is correct
4	Correct	1215 ms	132756 KB	Output is correct
5	Correct	780 ms	133224 KB	Output is correct
6	Correct	1108 ms	129956 KB	Output is correct
7	Correct	1061 ms	129696 KB	Output is correct
8	Correct	930 ms	130628 KB	Output is correct
9	Correct	1155 ms	129756 KB	Output is correct
10	Correct	1008 ms	129560 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	4 ms	1536 KB	Output is correct
3	Correct	4 ms	1536 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	3 ms	1536 KB	Output is correct
6	Correct	4 ms	1664 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	740 KB	Output is correct
9	Correct	4 ms	1664 KB	Output is correct
10	Correct	3 ms	1536 KB	Output is correct
11	Correct	3 ms	1536 KB	Output is correct
12	Correct	1501 ms	135844 KB	Output is correct
13	Correct	2676 ms	132360 KB	Output is correct
14	Correct	1043 ms	132396 KB	Output is correct
15	Correct	3116 ms	132716 KB	Output is correct
16	Correct	400 ms	132444 KB	Output is correct
17	Correct	2356 ms	133356 KB	Output is correct
18	Correct	2946 ms	133064 KB	Output is correct
19	Correct	2765 ms	133192 KB	Output is correct
20	Correct	2487 ms	132384 KB	Output is correct
21	Correct	2 ms	384 KB	Output is correct

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	1664 KB	Output is correct
3	Correct	4 ms	1536 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	3 ms	1664 KB	Output is correct
6	Correct	3 ms	1664 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	2 ms	768 KB	Output is correct
9	Correct	3 ms	1536 KB	Output is correct
10	Correct	4 ms	1536 KB	Output is correct
11	Correct	3 ms	1536 KB	Output is correct
12	Correct	1142 ms	133036 KB	Output is correct
13	Correct	741 ms	133368 KB	Output is correct
14	Correct	1069 ms	130284 KB	Output is correct
15	Correct	1134 ms	129904 KB	Output is correct
16	Correct	926 ms	130816 KB	Output is correct
17	Correct	1175 ms	129932 KB	Output is correct
18	Correct	939 ms	129668 KB	Output is correct
19	Correct	1564 ms	136124 KB	Output is correct
20	Correct	2639 ms	132680 KB	Output is correct
21	Correct	1104 ms	137072 KB	Output is correct
22	Correct	3229 ms	137064 KB	Output is correct
23	Correct	399 ms	136672 KB	Output is correct
24	Correct	2259 ms	137844 KB	Output is correct
25	Correct	2758 ms	138192 KB	Output is correct
26	Correct	2692 ms	138296 KB	Output is correct
27	Correct	2646 ms	137764 KB	Output is correct
28	Runtime error	6 ms	640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	4 ms	1664 KB	Output is correct
3	Correct	4 ms	1536 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	4 ms	1536 KB	Output is correct
6	Correct	3 ms	1536 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	768 KB	Output is correct
9	Correct	3 ms	1536 KB	Output is correct
10	Correct	4 ms	1536 KB	Output is correct
11	Correct	3 ms	1536 KB	Output is correct
12	Correct	1133 ms	132992 KB	Output is correct
13	Correct	769 ms	133548 KB	Output is correct
14	Correct	1016 ms	130240 KB	Output is correct
15	Correct	1136 ms	130040 KB	Output is correct
16	Correct	952 ms	130812 KB	Output is correct
17	Correct	1084 ms	130168 KB	Output is correct
18	Correct	952 ms	129672 KB	Output is correct
19	Correct	1535 ms	136168 KB	Output is correct
20	Correct	2631 ms	132728 KB	Output is correct
21	Correct	1153 ms	137024 KB	Output is correct
22	Correct	3094 ms	137020 KB	Output is correct
23	Correct	386 ms	136696 KB	Output is correct
24	Correct	2316 ms	137892 KB	Output is correct
25	Correct	2560 ms	138184 KB	Output is correct
26	Correct	2674 ms	138208 KB	Output is correct
27	Correct	2780 ms	137676 KB	Output is correct
28	Runtime error	4 ms	640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Halted	0 ms	0 KB	-

답안 #97698

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0