| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 5239 |
2014-02-21T15:26:39 Z |
ainta |
Game (IOI13_game) |
C++ |
|
0 ms |
1208 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->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 0;// Calc(root, 1, rr, P + 1, Q + 1, U + 1, V + 1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
