답안 #937956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937956	2024-03-04T17:11:15 Z	Muaath_5	게임 (IOI13_game)	C++17	100 / 100	2769 ms	88232 KB

game

#include <bits/stdc++.h>

#include "game.h"

using namespace std;


int const R = 1 << 30, C = 1 << 30;

//                     ^ really good programming language


struct NodeY

{

    unique_ptr<NodeY> l, r;

    int a, b;

    long long g;


    NodeY(int a_, int b_) { a = a_, b = b_; }


    void update(int Q, long long K)

    {

        if (a == b)

        {

            g = K;

            return;

        }


        if (l && 2 * (l->b - l->a + 1) != b - a + 1)

        {

            unique_ptr<NodeY> y = move(l);

            l = make_unique<NodeY>(a, (a + b) / 2);

            (y->b <= (l->a + l->b) / 2 ? l->l : l->r) = move(y);

        }

        if (r && 2 * (r->b - r->a + 1) != b - a + 1)

        {

            unique_ptr<NodeY> y = move(r);

            r = make_unique<NodeY>((a + b) / 2 + 1, b);

            (y->b <= (r->a + r->b) / 2 ? r->l : r->r) = move(y);

        }


        if (Q <= (a + b) / 2)

            (l ? l : l = make_unique<NodeY>(a, (a + b) / 2))->update(Q, K);

        else

            (r ? r : r = make_unique<NodeY>((a + b) / 2 + 1, b))->update(Q, K);


        if (l && (!l->l ^ !l->r))

            l = move(l->l ? l->l : l->r);

        if (r && (!r->l ^ !r->r))

            r = move(r->l ? r->l : r->r);

        g = gcd(l ? l->g : 0, r ? r->g : 0);

    }


    long long calculate(int Q, int V)

    {

        if (b < Q || a > V)

            return 0;

        if (Q <= a && b <= V)

            return g;

        return gcd(l ? l->calculate(Q, V) : 0, r ? r->calculate(Q, V) : 0);

    }

};


struct NodeX

{

    unique_ptr<NodeX> l, r;

    unique_ptr<NodeY> y;


    void update(int P, int Q, long long K, int A, int B)

    {

        if (!y)

            y = make_unique<NodeY>(0, C - 1);

        if (A == B)

        {

            y->update(Q, K);

            return;

        }


        if (P <= (A + B) / 2)

            (l ? l : l = make_unique<NodeX>())->update(P, Q, K, A, (A + B) / 2);

        else

            (r ? r : r = make_unique<NodeX>())->update(P, Q, K, (A + B) / 2 + 1, B);


        y->update(Q, gcd(l && l->y ? l->y->calculate(Q, Q) : 0,

                         r && r->y ? r->y->calculate(Q, Q) : 0));

    }


    long long calculate(int P, int Q, int U, int V, int A, int B)

    {

        if (B < P || A > U)

            return 0;

        if (P <= A && B <= U)

            return y ? y->calculate(Q, V) : 0;

        return gcd(l ? l->calculate(P, Q, U, V, A, (A + B) / 2) : 0,

                   r ? r->calculate(P, Q, U, V, (A + B) / 2 + 1, B) : 0);

    }

};


NodeX root;


void init(int R, int C) {}


void update(int P, int Q, long long K) { root.update(P, Q, K, 0, R - 1); }


long long calculate(int P, int Q, int U, int V) { return root.calculate(P, Q, U, V, 0, R - 1); }

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	3 ms	600 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	3 ms	856 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	3 ms	604 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	0 ms	344 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	714 ms	32088 KB	Output is correct
5	Correct	555 ms	32432 KB	Output is correct
6	Correct	839 ms	29356 KB	Output is correct
7	Correct	858 ms	29040 KB	Output is correct
8	Correct	489 ms	15632 KB	Output is correct
9	Correct	844 ms	29204 KB	Output is correct
10	Correct	854 ms	28848 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	3 ms	604 KB	Output is correct
3	Correct	4 ms	856 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	4 ms	600 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	3 ms	604 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	908 ms	13496 KB	Output is correct
13	Correct	1266 ms	6848 KB	Output is correct
14	Correct	439 ms	1584 KB	Output is correct
15	Correct	1350 ms	9588 KB	Output is correct
16	Correct	509 ms	13812 KB	Output is correct
17	Correct	724 ms	9808 KB	Output is correct
18	Correct	1286 ms	14160 KB	Output is correct
19	Correct	1150 ms	14160 KB	Output is correct
20	Correct	1165 ms	13768 KB	Output is correct
21	Correct	1 ms	344 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	3 ms	604 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	500 KB	Output is correct
6	Correct	3 ms	604 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	3 ms	604 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	803 ms	32100 KB	Output is correct
13	Correct	636 ms	32236 KB	Output is correct
14	Correct	886 ms	29224 KB	Output is correct
15	Correct	968 ms	28908 KB	Output is correct
16	Correct	468 ms	15604 KB	Output is correct
17	Correct	1030 ms	28992 KB	Output is correct
18	Correct	820 ms	28828 KB	Output is correct
19	Correct	862 ms	13420 KB	Output is correct
20	Correct	1261 ms	7008 KB	Output is correct
21	Correct	421 ms	1104 KB	Output is correct
22	Correct	1397 ms	9580 KB	Output is correct
23	Correct	526 ms	14372 KB	Output is correct
24	Correct	715 ms	9912 KB	Output is correct
25	Correct	1302 ms	13904 KB	Output is correct
26	Correct	1132 ms	14260 KB	Output is correct
27	Correct	1164 ms	13904 KB	Output is correct
28	Correct	584 ms	36176 KB	Output is correct
29	Correct	1242 ms	48192 KB	Output is correct
30	Correct	1679 ms	36916 KB	Output is correct
31	Correct	1560 ms	29900 KB	Output is correct
32	Correct	451 ms	10540 KB	Output is correct
33	Correct	544 ms	10708 KB	Output is correct
34	Correct	657 ms	42100 KB	Output is correct
35	Correct	805 ms	28520 KB	Output is correct
36	Correct	1686 ms	46344 KB	Output is correct
37	Correct	1391 ms	46372 KB	Output is correct
38	Correct	1371 ms	45860 KB	Output is correct
39	Correct	1137 ms	38188 KB	Output is correct
40	Correct	1 ms	348 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	4 ms	604 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	3 ms	600 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	3 ms	448 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	749 ms	32172 KB	Output is correct
13	Correct	603 ms	32588 KB	Output is correct
14	Correct	786 ms	29300 KB	Output is correct
15	Correct	835 ms	29164 KB	Output is correct
16	Correct	472 ms	15764 KB	Output is correct
17	Correct	959 ms	29056 KB	Output is correct
18	Correct	810 ms	28964 KB	Output is correct
19	Correct	872 ms	13628 KB	Output is correct
20	Correct	1260 ms	7204 KB	Output is correct
21	Correct	425 ms	992 KB	Output is correct
22	Correct	1380 ms	9812 KB	Output is correct
23	Correct	524 ms	13644 KB	Output is correct
24	Correct	690 ms	9648 KB	Output is correct
25	Correct	1377 ms	14072 KB	Output is correct
26	Correct	1171 ms	14160 KB	Output is correct
27	Correct	1088 ms	13856 KB	Output is correct
28	Correct	557 ms	37456 KB	Output is correct
29	Correct	1208 ms	48680 KB	Output is correct
30	Correct	1664 ms	37020 KB	Output is correct
31	Correct	1520 ms	29992 KB	Output is correct
32	Correct	453 ms	10228 KB	Output is correct
33	Correct	562 ms	10836 KB	Output is correct
34	Correct	640 ms	42096 KB	Output is correct
35	Correct	815 ms	28428 KB	Output is correct
36	Correct	1634 ms	46504 KB	Output is correct
37	Correct	1309 ms	46476 KB	Output is correct
38	Correct	1411 ms	45824 KB	Output is correct
39	Correct	1025 ms	87108 KB	Output is correct
40	Correct	2247 ms	88232 KB	Output is correct
41	Correct	2577 ms	70408 KB	Output is correct
42	Correct	2341 ms	55300 KB	Output is correct
43	Correct	1257 ms	82812 KB	Output is correct
44	Correct	746 ms	10836 KB	Output is correct
45	Correct	1075 ms	37932 KB	Output is correct
46	Correct	2680 ms	87008 KB	Output is correct
47	Correct	2769 ms	86816 KB	Output is correct
48	Correct	2608 ms	86436 KB	Output is correct
49	Correct	0 ms	348 KB	Output is correct

답안 #937956

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 20.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
20.0 / 20.0