답안 #8805 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8805	2014-09-18T17:06:03 Z	baneling100	게임 (IOI13_game)	C++	80 / 100	4496 ms	256000 KB

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.0 / 10.0

#	결과	메모리	Grader output
1	Correct	1208 KB	Output is correct
2	Correct	1208 KB	Output is correct
3	Correct	1208 KB	Output is correct
4	Correct	1208 KB	Output is correct
5	Correct	1208 KB	Output is correct
6	Correct	1208 KB	Output is correct
7	Correct	1208 KB	Output is correct
8	Correct	1208 KB	Output is correct
9	Correct	1208 KB	Output is correct
10	Correct	1208 KB	Output is correct
11	Correct	1208 KB	Output is correct
12	Correct	1208 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #8805

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 0.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
0.0 / 20.0