oj.uz

Submission #4653

# Submission time Handle Problem Language Result Execution time Memory
4653 2013-11-15T19:27:39 Z ainta Game (IOI13_game) C++
100 / 100
 10360 ms 84764 KB 
#include "game.h"
#include <stdio.h>
#include <algorithm>
using namespace std;

int N, M;

struct Y_Seg{
	Y_Seg *c1, *c2;
	int b;
	long long G;
	Y_Seg(int p){ c1 = c2 = NULL, G = 0, b = p; }
};

struct X_Seg{
	X_Seg *c1, *c2;
	Y_Seg *cy;
	X_Seg(){ c1 = c2 = NULL, cy = NULL; }
};

X_Seg *root;

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

void init(int R, int C) {
	N = R, M = C;
	root = new X_Seg();
}

void UDT_Y(Y_Seg *node, int b, int e, int y, long long K){
	int t, m = (b + e) >> 1;
	if (node->b){
		if (node->b == y){
			node->G = K;
			return;
		}
		else{
			t = node->b;
			node->b = 0;
			if (t <= m){
				node->c1 = new Y_Seg(t);
				node->c1->G = node->G;
			}
			else{
				node->c2 = new Y_Seg(t);
				node->c2->G = node->G;
			}
		}
	}
	if (y <= m){
		if (!node->c1)node->c1 = new Y_Seg(y);
		UDT_Y(node->c1, b, m, y, K);
	}
	else{
		if (!node->c2)node->c2 = new Y_Seg(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_Leaf(X_Seg *node, int y){
	if (node == NULL)return 0;
	Y_Seg *p = node->cy;
	int b = 1, e = M, m;
	while (p != NULL){
		if (p->b){
			return p->b == y ? p->G : 0;
		}
		m = (b + e) >> 1;
		if (m >= y) p = p->c1, e = m;
		else p = p->c2, b = m + 1;
	}
	return 0;
}

void UDT_X(X_Seg *node, int b, int e, int x, int y, long long K){
	if (!node->cy)node->cy = new Y_Seg(y);
	if (b == e){
		UDT_Y(node->cy, 1, M, y, K);
		return;
	}
	int m = (b + e) >> 1;
	long long G = 0;
	if (x <= m){
		if (!node->c1)node->c1 = new X_Seg();
		UDT_X(node->c1, b, m, x, y, K);
	}
	else{
		if (!node->c2)node->c2 = new X_Seg();
		UDT_X(node->c2, m + 1, e, x, y, K);
	}
	G = gcd2(Gap_Leaf(node->c1, y), Gap_Leaf(node->c2, y));
	UDT_Y(node->cy, 1, M, y, G);
}

void update(int P, int Q, long long K) {
	UDT_X(root, 1, N, P+1, Q+1, K);
}

long long CalcY(Y_Seg *node, int b, int e, int s, int l){
	if (!node)return 0;
	if (node->b){
		if (s <= node->b && node->b <= l) return node->G;
		return 0;
	}
	if (b == s && e == l)return node->G;
	int m = (b + e) >> 1;
	long long G = 0;
	if (m >= s && node->c1)G = CalcY(node->c1, b, m, s, min(l, m));
	if (m < l && node->c2)G = gcd2(G, CalcY(node->c2, m + 1, e, max(s, m + 1), l));
	return G;
}

long long CalcX(X_Seg *node, int b, int e, int P, int Q, int U, int V){
	int m = (b + e) >> 1;
	if (b == P && e == U){
		return CalcY(node->cy, 1, M, Q, V);
	}
	long long G = 0;
	if (m >= P){
		if (node->c1)G = CalcX(node->c1, b, m, P, Q, min(m, U), V);
	}
	if (m < U){
		if (node->c2)G = gcd2(G, CalcX(node->c2, m + 1, e, max(P, m + 1), Q, U, V));
	}
	return G;
}

long long calculate(int P, int Q, int U, int V) {
	return CalcX(root, 1, N, 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 788 ms 5828 KB Output is correct
5 Correct 532 ms 5828 KB Output is correct
6 Correct 708 ms 5960 KB Output is correct
7 Correct 808 ms 5960 KB Output is correct
8 Correct 500 ms 3452 KB Output is correct
9 Correct 772 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 1288 ms 9260 KB Output is correct
13 Correct 3068 ms 5960 KB Output is correct
14 Correct 400 ms 1340 KB Output is correct
15 Correct 3588 ms 7544 KB Output is correct
16 Correct 268 ms 11372 KB Output is correct
17 Correct 1188 ms 6488 KB Output is correct
18 Correct 2076 ms 11372 KB Output is correct
19 Correct 1680 ms 11372 KB Output is correct
20 Correct 1604 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 780 ms 5828 KB Output is correct
13 Correct 516 ms 5828 KB Output is correct
14 Correct 700 ms 5960 KB Output is correct
15 Correct 780 ms 5960 KB Output is correct
16 Correct 500 ms 3452 KB Output is correct
17 Correct 752 ms 5960 KB Output is correct
18 Correct 672 ms 5960 KB Output is correct
19 Correct 1264 ms 9260 KB Output is correct
20 Correct 3088 ms 5960 KB Output is correct
21 Correct 412 ms 1340 KB Output is correct
22 Correct 3584 ms 7544 KB Output is correct
23 Correct 280 ms 11372 KB Output is correct
24 Correct 1176 ms 6488 KB Output is correct
25 Correct 2032 ms 11372 KB Output is correct
26 Correct 1712 ms 11372 KB Output is correct
27 Correct 1604 ms 11372 KB Output is correct
28 Correct 728 ms 37904 KB Output is correct
29 Correct 1952 ms 30380 KB Output is correct
30 Correct 7980 ms 36716 KB Output is correct
31 Correct 7384 ms 27740 KB Output is correct
32 Correct 872 ms 1736 KB Output is correct
33 Correct 1112 ms 5300 KB Output is correct
34 Correct 372 ms 30380 KB Output is correct
35 Correct 1476 ms 15332 KB Output is correct
36 Correct 2640 ms 30380 KB Output is correct
37 Correct 2208 ms 30512 KB Output is correct
38 Correct 2104 ms 30512 KB Output is correct
39 Correct 1852 ms 23384 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 804 ms 5828 KB Output is correct
13 Correct 520 ms 5828 KB Output is correct
14 Correct 704 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 784 ms 5960 KB Output is correct
18 Correct 668 ms 5960 KB Output is correct
19 Correct 1268 ms 9260 KB Output is correct
20 Correct 3060 ms 5960 KB Output is correct
21 Correct 388 ms 1340 KB Output is correct
22 Correct 3560 ms 7544 KB Output is correct
23 Correct 272 ms 11372 KB Output is correct
24 Correct 1164 ms 6488 KB Output is correct
25 Correct 2020 ms 11372 KB Output is correct
26 Correct 1716 ms 11372 KB Output is correct
27 Correct 1552 ms 11372 KB Output is correct
28 Correct 700 ms 37904 KB Output is correct
29 Correct 1996 ms 30380 KB Output is correct
30 Correct 7984 ms 36716 KB Output is correct
31 Correct 7684 ms 27740 KB Output is correct
32 Correct 856 ms 1736 KB Output is correct
33 Correct 1104 ms 5300 KB Output is correct
34 Correct 368 ms 30380 KB Output is correct
35 Correct 1492 ms 15332 KB Output is correct
36 Correct 2656 ms 30380 KB Output is correct
37 Correct 2148 ms 30512 KB Output is correct
38 Correct 2068 ms 30512 KB Output is correct
39 Correct 964 ms 84764 KB Output is correct
40 Correct 3076 ms 66416 KB Output is correct
41 Correct 10360 ms 78692 KB Output is correct
42 Correct 9776 ms 59288 KB Output is correct
43 Correct 672 ms 66416 KB Output is correct
44 Correct 1172 ms 1736 KB Output is correct
45 Correct 1880 ms 23384 KB Output is correct
46 Correct 3444 ms 66416 KB Output is correct
47 Correct 3384 ms 66548 KB Output is correct
48 Correct 3276 ms 66416 KB Output is correct
49 Correct 0 ms 1208 KB Output is correct