oj.uz

Submission #8805

# Submission time Handle Problem Language Result Execution time Memory
8805 2014-09-18T17:06:03 Z baneling100 Game (IOI13_game) C++
80 / 100
 4496 ms 256000 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 = 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.0 / 10.0

# 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 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 0 ms 1208 KB Output is correct

Subtask #2
27.0 / 27.0

# 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 Correct 644 ms 9788 KB Output is correct
5 Correct 396 ms 9788 KB Output is correct
6 Correct 556 ms 9788 KB Output is correct
7 Correct 632 ms 9788 KB Output is correct
8 Correct 412 ms 5960 KB Output is correct
9 Correct 588 ms 9788 KB Output is correct
10 Correct 488 ms 9656 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct

Subtask #3
26.0 / 26.0

# 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 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 1404 ms 12692 KB Output is correct
13 Correct 2140 ms 6356 KB Output is correct
14 Correct 296 ms 1208 KB Output is correct
15 Correct 2404 ms 8600 KB Output is correct
16 Correct 376 ms 18368 KB Output is correct
17 Correct 872 ms 10976 KB Output is correct
18 Correct 1460 ms 18368 KB Output is correct
19 Correct 1260 ms 18368 KB Output is correct
20 Correct 1092 ms 18368 KB Output is correct
21 Correct 0 ms 1208 KB Output is correct

Subtask #4
17.0 / 17.0

# 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 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 652 ms 9788 KB Output is correct
13 Correct 420 ms 9788 KB Output is correct
14 Correct 552 ms 9788 KB Output is correct
15 Correct 600 ms 9788 KB Output is correct
16 Correct 420 ms 5960 KB Output is correct
17 Correct 588 ms 9788 KB Output is correct
18 Correct 488 ms 9656 KB Output is correct
19 Correct 1416 ms 12692 KB Output is correct
20 Correct 2132 ms 6356 KB Output is correct
21 Correct 300 ms 1208 KB Output is correct
22 Correct 2408 ms 8600 KB Output is correct
23 Correct 364 ms 18368 KB Output is correct
24 Correct 900 ms 10976 KB Output is correct
25 Correct 1464 ms 18368 KB Output is correct
26 Correct 1232 ms 18368 KB Output is correct
27 Correct 1072 ms 18368 KB Output is correct
28 Correct 672 ms 99020 KB Output is correct
29 Correct 2000 ms 121328 KB Output is correct
30 Correct 4480 ms 75392 KB Output is correct
31 Correct 4304 ms 57044 KB Output is correct
32 Correct 452 ms 1340 KB Output is correct
33 Correct 660 ms 2132 KB Output is correct
34 Correct 716 ms 121328 KB Output is correct
35 Correct 1236 ms 57968 KB Output is correct
36 Correct 2328 ms 121328 KB Output is correct
37 Correct 1880 ms 121328 KB Output is correct
38 Correct 1720 ms 121328 KB Output is correct
39 Correct 1560 ms 91100 KB Output is correct
40 Correct 0 ms 1208 KB Output is correct

Subtask #5
0.0 / 20.0

# 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 Correct 0 ms 1208 KB Output is correct
5 Correct 0 ms 1208 KB Output is correct
6 Correct 0 ms 1208 KB Output is correct
7 Correct 0 ms 1208 KB Output is correct
8 Correct 0 ms 1208 KB Output is correct
9 Correct 0 ms 1208 KB Output is correct
10 Correct 0 ms 1208 KB Output is correct
11 Correct 0 ms 1208 KB Output is correct
12 Correct 668 ms 9788 KB Output is correct
13 Correct 388 ms 9788 KB Output is correct
14 Correct 556 ms 9788 KB Output is correct
15 Correct 592 ms 9788 KB Output is correct
16 Correct 400 ms 5960 KB Output is correct
17 Correct 588 ms 9788 KB Output is correct
18 Correct 512 ms 9656 KB Output is correct
19 Correct 1424 ms 12692 KB Output is correct
20 Correct 2148 ms 6356 KB Output is correct
21 Correct 304 ms 1208 KB Output is correct
22 Correct 2388 ms 8600 KB Output is correct
23 Correct 384 ms 18368 KB Output is correct
24 Correct 896 ms 10976 KB Output is correct
25 Correct 1492 ms 18368 KB Output is correct
26 Correct 1260 ms 18368 KB Output is correct
27 Correct 1088 ms 18368 KB Output is correct
28 Correct 712 ms 99020 KB Output is correct
29 Correct 1996 ms 121328 KB Output is correct
30 Correct 4496 ms 75392 KB Output is correct
31 Correct 4272 ms 57044 KB Output is correct
32 Correct 432 ms 1340 KB Output is correct
33 Correct 636 ms 2132 KB Output is correct
34 Correct 724 ms 121328 KB Output is correct
35 Correct 1240 ms 57968 KB Output is correct
36 Correct 2324 ms 121328 KB Output is correct
37 Correct 1896 ms 121328 KB Output is correct
38 Correct 1780 ms 121328 KB Output is correct
39 Correct 1000 ms 218216 KB Output is correct
40 Memory limit exceeded 2812 ms 256000 KB Memory limit exceeded
41 Halted 0 ms 0 KB -