oj.uz

Submission #97698

# Submission time Handle Problem Language Result Execution time Memory
97698 2019-02-17T18:11:36 Z tincamatei Game (IOI13_game) C++14
63 / 100
 3229 ms 138296 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -