oj.uz

Submission #5241

# Submission time Handle Problem Language Result Execution time Memory
5241 2014-02-21T15:28:14 Z ainta Game (IOI13_game) C++
100 / 100
 9400 ms 105488 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);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 0 ms 1208 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 824 ms 5828 KB Output is correct
5 Correct 580 ms 5828 KB Output is correct
6 Correct 760 ms 5960 KB Output is correct
7 Correct 840 ms 5960 KB Output is correct
8 Correct 496 ms 3452 KB Output is correct
9 Correct 844 ms 5960 KB Output is correct
10 Correct 692 ms 5960 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 1384 ms 9260 KB Output is correct
13 Correct 3160 ms 5960 KB Output is correct
14 Correct 412 ms 1340 KB Output is correct
15 Correct 3684 ms 7676 KB Output is correct
16 Correct 296 ms 11372 KB Output is correct
17 Correct 1248 ms 6488 KB Output is correct
18 Correct 2316 ms 11504 KB Output is correct
19 Correct 1944 ms 11372 KB Output is correct
20 Correct 1716 ms 11372 KB Output is correct
21 Correct 0 ms 1208 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 792 ms 5828 KB Output is correct
13 Correct 536 ms 5828 KB Output is correct
14 Correct 700 ms 5960 KB Output is correct
15 Correct 804 ms 5960 KB Output is correct
16 Correct 492 ms 3452 KB Output is correct
17 Correct 776 ms 5960 KB Output is correct
18 Correct 676 ms 5960 KB Output is correct
19 Correct 1328 ms 9260 KB Output is correct
20 Correct 3100 ms 5960 KB Output is correct
21 Correct 380 ms 1340 KB Output is correct
22 Correct 3652 ms 7676 KB Output is correct
23 Correct 268 ms 11372 KB Output is correct
24 Correct 1264 ms 6488 KB Output is correct
25 Correct 2220 ms 11504 KB Output is correct
26 Correct 1800 ms 11372 KB Output is correct
27 Correct 1680 ms 11372 KB Output is correct
28 Correct 844 ms 48068 KB Output is correct
29 Correct 2152 ms 40544 KB Output is correct
30 Correct 7216 ms 42392 KB Output is correct
31 Correct 6456 ms 32096 KB Output is correct
32 Correct 820 ms 1736 KB Output is correct
33 Correct 1088 ms 5432 KB Output is correct
34 Correct 384 ms 40544 KB Output is correct
35 Correct 1572 ms 20744 KB Output is correct
36 Correct 2868 ms 40544 KB Output is correct
37 Correct 2316 ms 40676 KB Output is correct
38 Correct 2256 ms 40676 KB Output is correct
39 Correct 1960 ms 31304 KB Output is correct
40 Correct 0 ms 1208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1208 KB Output is correct
2 Correct 0 ms 1208 KB Output is correct
3 Correct 0 ms 1208 KB Output is correct
4 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 768 ms 5828 KB Output is correct
13 Correct 536 ms 5828 KB Output is correct
14 Correct 704 ms 5960 KB Output is correct
15 Correct 796 ms 5960 KB Output is correct
16 Correct 488 ms 3452 KB Output is correct
17 Correct 768 ms 5960 KB Output is correct
18 Correct 704 ms 5960 KB Output is correct
19 Correct 1320 ms 9260 KB Output is correct
20 Correct 2984 ms 5960 KB Output is correct
21 Correct 400 ms 1340 KB Output is correct
22 Correct 3664 ms 7676 KB Output is correct
23 Correct 292 ms 11372 KB Output is correct
24 Correct 1256 ms 6488 KB Output is correct
25 Correct 2176 ms 11504 KB Output is correct
26 Correct 1836 ms 11372 KB Output is correct
27 Correct 1656 ms 11372 KB Output is correct
28 Correct 772 ms 48068 KB Output is correct
29 Correct 2068 ms 40544 KB Output is correct
30 Correct 7176 ms 42392 KB Output is correct
31 Correct 6420 ms 32096 KB Output is correct
32 Correct 824 ms 1736 KB Output is correct
33 Correct 1108 ms 5432 KB Output is correct
34 Correct 396 ms 40544 KB Output is correct
35 Correct 1544 ms 20744 KB Output is correct
36 Correct 2812 ms 40544 KB Output is correct
37 Correct 2308 ms 40676 KB Output is correct
38 Correct 2208 ms 40676 KB Output is correct
39 Correct 1048 ms 105488 KB Output is correct
40 Correct 3192 ms 87140 KB Output is correct
41 Correct 9400 ms 90176 KB Output is correct
42 Correct 8744 ms 68000 KB Output is correct
43 Correct 732 ms 87272 KB Output is correct
44 Correct 1124 ms 1736 KB Output is correct
45 Correct 1992 ms 31304 KB Output is correct
46 Correct 3740 ms 87272 KB Output is correct
47 Correct 3712 ms 87272 KB Output is correct
48 Correct 3484 ms 87272 KB Output is correct
49 Correct 0 ms 1208 KB Output is correct