Submission #8803

#TimeUsernameProblemLanguageResultExecution timeMemory
8803baneling100Game (IOI13_game)C++98
0 / 100
0 ms1208 KiB
#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; 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->RightNode->InfoNode; else NowY->InfoNode = NowY->LeftNode->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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...