| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 8804 |
2014-09-18T16:11:47 Z |
baneling100 |
Game (IOI13_game) |
C++ |
|
648 ms |
9788 KB |
#include "game.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
struct NodeX {
NodeX(long long Value) : LeftNode(NULL), RightNode(NULL), Value(Value) {}
NodeX *LeftNode, *RightNode;
long long Value;
};
struct NodeY {
NodeY() : LeftNode(NULL), RightNode(NULL), InfoNode(NULL), RootX(NULL) {}
NodeY *LeftNode, *RightNode, *InfoNode;
NodeX *RootX;
} *RootY;
int R, C, P, Q, U, V;
long long K, Res;
long long gcd2(long long X, long long Y) {
long long tmp;
if(X && Y) {
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
return max(X, Y);
}
void init(int R_, int C_) {
for(R = 1 ; R < R_ ; R <<= 1);
for(C = 1 ; C < C_ ; C <<= 1);
RootY = new NodeY();
}
void ReNewX(int Left, int Right, NodeX *NowX) {
int Mid = (Left + Right) / 2;
if(Left == Right)
NowX->Value = K;
else {
if(Q <= Mid) {
if(NowX->LeftNode == NULL)
NowX->LeftNode = new NodeX(0);
ReNewX(Left, Mid, NowX->LeftNode);
}
else {
if(NowX->RightNode == NULL)
NowX->RightNode = new NodeX(0);
ReNewX(Mid + 1, Right, NowX->RightNode);
}
if(NowX->LeftNode == NULL)
NowX->Value = NowX->RightNode->Value;
else {
if(NowX->RightNode == NULL)
NowX->Value = NowX->LeftNode->Value;
else
NowX->Value = gcd2(NowX->LeftNode->Value, NowX->RightNode->Value);
}
}
}
void CombineNode(NodeX *NodeA, NodeX *NodeB) {
NodeA->Value = gcd2(NodeA->Value, NodeB->Value);
if(NodeB->LeftNode != NULL) {
if(NodeA->LeftNode == NULL)
NodeA->LeftNode = new NodeX(0);
CombineNode(NodeA->LeftNode, NodeB->LeftNode);
}
if(NodeB->RightNode != NULL) {
if(NodeA->RightNode == NULL)
NodeA->RightNode = new NodeX(0);
CombineNode(NodeA->RightNode, NodeB->RightNode);
}
}
void ReNewNode(int Left, int Right, NodeX *NodeA, NodeX *NodeB, NodeX *NodeC) {
int Mid = (Left + Right) / 2;
if(NodeB == NULL)
NodeA->Value = gcd2(0, NodeC->Value);
else {
if(NodeC == NULL)
NodeA->Value = gcd2(NodeB->Value, 0);
else
NodeA->Value = gcd2(NodeB->Value, NodeC->Value);
}
if(Left == Right)
return;
if(Q <= Mid) {
if(NodeA->LeftNode == NULL)
NodeA->LeftNode = new NodeX(0);
if(NodeB == NULL)
ReNewNode(Left, Mid, NodeA->LeftNode, NULL, NodeC->LeftNode);
else {
if(NodeC == NULL)
ReNewNode(Left, Mid, NodeA->LeftNode, NodeB->LeftNode, NULL);
else
ReNewNode(Left, Mid, NodeA->LeftNode, NodeB->LeftNode, NodeC->LeftNode);
}
}
else {
if(NodeA->RightNode == NULL)
NodeA->RightNode = new NodeX(0);
if(NodeB == NULL)
ReNewNode(Mid + 1, Right, NodeA->RightNode, NULL, NodeC->RightNode);
else {
if(NodeC == NULL)
ReNewNode(Mid + 1, Right, NodeA->RightNode, NodeB->RightNode, NULL);
else
ReNewNode(Mid + 1, Right, NodeA->RightNode, NodeB->RightNode, NodeC->RightNode);
}
}
}
void ReNewY(int Left, int Right, NodeY *NowY) {
int Mid = (Left + Right) / 2;
if(Left == Right) {
if(NowY->RootX == NULL)
NowY->RootX = new NodeX(0);
ReNewX(0, C - 1, NowY->RootX);
NowY->InfoNode = NowY;
}
else {
if(P <= Mid) {
if(NowY->LeftNode == NULL)
NowY->LeftNode = new NodeY();
ReNewY(Left, Mid, NowY->LeftNode);
}
else {
if(NowY->RightNode == NULL)
NowY->RightNode = new NodeY();
ReNewY(Mid + 1, Right, NowY->RightNode);
}
if(NowY->LeftNode != NULL && NowY->RightNode != NULL) {
NowY->InfoNode = NowY;
if(NowY->RootX == NULL) {
NowY->RootX = new NodeX(0);
CombineNode(NowY->RootX, NowY->LeftNode->InfoNode->RootX);
CombineNode(NowY->RootX, NowY->RightNode->InfoNode->RootX);
}
else
ReNewNode(0, C - 1, NowY->RootX, NowY->LeftNode->InfoNode->RootX, NowY->RightNode->InfoNode->RootX);
}
else {
if(NowY->LeftNode != NULL)
NowY->InfoNode = NowY->LeftNode->InfoNode;
else
NowY->InfoNode = NowY->RightNode->InfoNode;
}
}
}
void update(int P_, int Q_, long long K_) {
P = P_;
Q = Q_;
K = K_;
ReNewY(0, R - 1, RootY);
}
void FindX(int Left, int Right, NodeX *NowX) {
int Mid = (Left + Right) / 2;
if(Q <= Left && Right <= V)
Res = gcd2(Res, NowX->Value);
else {
if(Q <= Mid && NowX->LeftNode != NULL)
FindX(Left, Mid, NowX->LeftNode);
if(Mid + 1 <= V && NowX->RightNode != NULL)
FindX(Mid + 1, Right, NowX->RightNode);
}
}
void FindY(int Left, int Right, NodeY *NowY) {
int Mid = (Left + Right) / 2;
if(P <= Left && Right <= U) {
if(NowY->InfoNode != NULL)
FindX(0, C - 1, NowY->InfoNode->RootX);
}
else {
if(P <= Mid && NowY->LeftNode != NULL)
FindY(Left, Mid, NowY->LeftNode);
if(Mid + 1 <= Q && NowY->RightNode != NULL)
FindY(Mid + 1, Right, NowY->RightNode);
}
}
long long calculate(int P_, int Q_, int U_, int V_) {
P = P_;
Q = Q_;
U = U_;
V = V_;
Res = 0;
FindY(0, R - 1, RootY);
return Res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
648 ms |
9788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1208 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1208 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
