oj.uz

Submission #120077

# Submission time Handle Problem Language Result Execution time Memory
120077 2019-06-23T08:22:33 Z nvmdava Game (IOI13_game) C++17
100 / 100
 6324 ms 116244 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
#include "game.h"
 
int rr, cc;
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 Seg_Y{
	Seg_Y *c1, *c2;
	int K;
	long long G;
	Seg_Y(int p){ c1 = c2 = NULL, K = p, G = 0; }
};
 
struct Seg_X{
	Seg_X *c1, *c2;
	Seg_Y *cy;
	long long G;
};
Seg_X *root;
 
void init(int R, int C) {
	root = new Seg_X();
	rr = R, cc = C;
}
 
void UDT_Y(Seg_Y *node, int b, int e, int y, long long K){
	int m = (b + e) >> 1;
	if (node->K){
		if (node->K == y){
			node->G = K;
			return;
		}
		if (node->K <= m)node->c1 = new Seg_Y(node->K), node->c1->G = node->G;
		else node->c2 = new Seg_Y(node->K), node->c2->G = node->G;
		node->K = 0;
	}
	if (y <= m){
		if (!node->c1) node->c1 = new Seg_Y(y);
		UDT_Y(node->c1, b, m, y, K);
	}
	else {
		if (!node->c2) node->c2 = new Seg_Y(y);
		UDT_Y(node->c2, m + 1, e, y, K);
	}
	node->G = gcd2(node->c1 ? node->c1->G : 0, node->c2 ? node->c2->G : 0);
}
 
long long Gap(Seg_Y *node, int b, int e, int y){
	if (node == NULL)return 0;
	if (node->K){
		if (node->K == y)return node->G;
		return 0;
	}
	int m = (b + e) >> 1;
	if (y <= m)return Gap(node->c1, b, m, y);
	else return Gap(node->c2, m + 1, e, y);
}
 
void UDT_X(Seg_X *node, int b, int e, int x, int y, long long K){
	if (!node->cy)node->cy = new Seg_Y(y);
	if (b == e){
		UDT_Y(node->cy, 1, cc, y, K);
		return;
	}
	int m = (b + e) >> 1;
	long long r = 0;
	if (!node->c1)node->c1 = new Seg_X();
	if (!node->c2)node->c2 = new Seg_X();
	if (x <= m)UDT_X(node->c1, b, m, x, y, K);
	else UDT_X(node->c2, m + 1, e, x, y, K);
	r = Gap(node->c2->cy, 1, cc, y);
	r = gcd2(Gap(node->c1->cy, 1, cc, y), r);
	UDT_Y(node->cy, 1, cc, y, r);
}
 
void update(int P, int Q, long long K) {
	UDT_X(root, 1, rr, P + 1, Q + 1, K);
}
 
long long Calc2(Seg_Y *node, int b, int e, int Q, int V){
	if (!node)return 0;
	if (node->K){
		if (node->K >= Q && node->K <= V)return node->G;
		return 0;
	}
	if (b == Q && e == V)return node->G;
	int m = (b + e) >> 1;
	long long r = 0;
	if (Q <= m && node->c1)r = Calc2(node->c1, b, m, Q, min(V,m));
	if (V > m && node->c2)r = gcd2(Calc2(node->c2, m + 1, e, max(m + 1, Q), V), r);
	return r;
}
long long Calc(Seg_X *node, int b, int e, int P, int Q, int U, int V){
	if (b == P && e == U)return Calc2(node->cy, 1, cc, Q, V);
	int m = (b + e) >> 1;
	long long r = 0;
	if (P <= m && node->c1) r = Calc(node->c1, b, m, P, Q, min(U, m), V);
	if (U > m && node->c2) r = gcd2(Calc(node->c2, m + 1, e, max(P, m + 1), Q, U, V), r);
	return r;
}
 
long long calculate(int P, int Q, int U, int V) {
	return  Calc(root, 1, rr, P + 1, Q + 1, U + 1, V + 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 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 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 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 564 ms 9080 KB Output is correct
5 Correct 385 ms 9324 KB Output is correct
6 Correct 608 ms 6316 KB Output is correct
7 Correct 758 ms 6108 KB Output is correct
8 Correct 394 ms 4384 KB Output is correct
9 Correct 651 ms 6008 KB Output is correct
10 Correct 542 ms 5708 KB Output is correct
11 Correct 2 ms 384 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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1028 ms 12540 KB Output is correct
13 Correct 2363 ms 6128 KB Output is correct
14 Correct 294 ms 1016 KB Output is correct
15 Correct 2696 ms 7576 KB Output is correct
16 Correct 255 ms 11384 KB Output is correct
17 Correct 1083 ms 7160 KB Output is correct
18 Correct 2218 ms 11896 KB Output is correct
19 Correct 1826 ms 12024 KB Output is correct
20 Correct 1556 ms 11388 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 569 ms 9088 KB Output is correct
13 Correct 380 ms 9484 KB Output is correct
14 Correct 567 ms 6264 KB Output is correct
15 Correct 683 ms 6136 KB Output is correct
16 Correct 389 ms 4344 KB Output is correct
17 Correct 627 ms 6264 KB Output is correct
18 Correct 548 ms 5736 KB Output is correct
19 Correct 940 ms 12664 KB Output is correct
20 Correct 2272 ms 5880 KB Output is correct
21 Correct 296 ms 1272 KB Output is correct
22 Correct 2731 ms 7800 KB Output is correct
23 Correct 247 ms 11384 KB Output is correct
24 Correct 1142 ms 7164 KB Output is correct
25 Correct 2158 ms 12024 KB Output is correct
26 Correct 1572 ms 11824 KB Output is correct
27 Correct 1494 ms 11256 KB Output is correct
28 Correct 734 ms 50024 KB Output is correct
29 Correct 1630 ms 53752 KB Output is correct
30 Correct 4993 ms 49372 KB Output is correct
31 Correct 4274 ms 39116 KB Output is correct
32 Correct 530 ms 10788 KB Output is correct
33 Correct 802 ms 14248 KB Output is correct
34 Correct 351 ms 47480 KB Output is correct
35 Correct 1424 ms 31224 KB Output is correct
36 Correct 3129 ms 51544 KB Output is correct
37 Correct 2402 ms 51792 KB Output is correct
38 Correct 2164 ms 51192 KB Output is correct
39 Correct 1936 ms 42032 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 593 ms 9200 KB Output is correct
13 Correct 372 ms 9472 KB Output is correct
14 Correct 625 ms 6560 KB Output is correct
15 Correct 738 ms 6136 KB Output is correct
16 Correct 408 ms 4420 KB Output is correct
17 Correct 679 ms 6264 KB Output is correct
18 Correct 536 ms 5932 KB Output is correct
19 Correct 921 ms 12572 KB Output is correct
20 Correct 2288 ms 6180 KB Output is correct
21 Correct 298 ms 1188 KB Output is correct
22 Correct 2721 ms 7896 KB Output is correct
23 Correct 232 ms 11512 KB Output is correct
24 Correct 1315 ms 7344 KB Output is correct
25 Correct 2285 ms 11984 KB Output is correct
26 Correct 1690 ms 12036 KB Output is correct
27 Correct 1568 ms 11512 KB Output is correct
28 Correct 734 ms 50168 KB Output is correct
29 Correct 1756 ms 53656 KB Output is correct
30 Correct 4689 ms 49296 KB Output is correct
31 Correct 4458 ms 39192 KB Output is correct
32 Correct 553 ms 10844 KB Output is correct
33 Correct 830 ms 14264 KB Output is correct
34 Correct 337 ms 47352 KB Output is correct
35 Correct 1494 ms 31272 KB Output is correct
36 Correct 3195 ms 51576 KB Output is correct
37 Correct 2450 ms 51780 KB Output is correct
38 Correct 2228 ms 51320 KB Output is correct
39 Correct 983 ms 116244 KB Output is correct
40 Correct 2657 ms 99812 KB Output is correct
41 Correct 6324 ms 97788 KB Output is correct
42 Correct 6238 ms 75480 KB Output is correct
43 Correct 720 ms 94712 KB Output is correct
44 Correct 695 ms 11256 KB Output is correct
45 Correct 1878 ms 42232 KB Output is correct
46 Correct 3924 ms 98840 KB Output is correct
47 Correct 3877 ms 98700 KB Output is correct
48 Correct 3765 ms 98364 KB Output is correct
49 Correct 2 ms 256 KB Output is correct