Submission #8805

#	Time	Username	Problem	Language	Result	Execution time	Memory
8805		baneling100	Game (IOI13_game)	C++98	80 / 100	4496 ms	256000 KiB

game

#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 = NodeC->Value;
    else {
        if(NodeC == NULL)
            NodeA->Value = NodeB->Value;
        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 <= U && 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;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20