| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 4650 |
2013-11-15T17:36:43 Z |
ainta |
Game (IOI13_game) |
C++ |
|
0 ms |
1204 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;
else p = p->c2;
}
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->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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1204 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
