oj.uz

Submission #722528

# Submission time Handle Problem Language Result Execution time Memory
722528 2023-04-12T08:14:28 Z finn__ Game (IOI13_game) C++17
100 / 100
 3367 ms 88140 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 940 ms 32112 KB Output is correct
5 Correct 762 ms 32320 KB Output is correct
6 Correct 1154 ms 29216 KB Output is correct
7 Correct 1264 ms 28904 KB Output is correct
8 Correct 596 ms 15472 KB Output is correct
9 Correct 1146 ms 28960 KB Output is correct
10 Correct 1205 ms 28688 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 7 ms 468 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 1289 ms 13488 KB Output is correct
13 Correct 1859 ms 6872 KB Output is correct
14 Correct 622 ms 924 KB Output is correct
15 Correct 1862 ms 9540 KB Output is correct
16 Correct 684 ms 13716 KB Output is correct
17 Correct 1028 ms 9628 KB Output is correct
18 Correct 1778 ms 14144 KB Output is correct
19 Correct 1581 ms 14112 KB Output is correct
20 Correct 1422 ms 13540 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 212 KB Output is correct
2 Correct 5 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 882 ms 32064 KB Output is correct
13 Correct 835 ms 32256 KB Output is correct
14 Correct 1082 ms 29268 KB Output is correct
15 Correct 1148 ms 29052 KB Output is correct
16 Correct 579 ms 15696 KB Output is correct
17 Correct 1040 ms 29008 KB Output is correct
18 Correct 1109 ms 29040 KB Output is correct
19 Correct 1108 ms 13384 KB Output is correct
20 Correct 1509 ms 7040 KB Output is correct
21 Correct 521 ms 932 KB Output is correct
22 Correct 1685 ms 9636 KB Output is correct
23 Correct 666 ms 13780 KB Output is correct
24 Correct 887 ms 9672 KB Output is correct
25 Correct 1768 ms 14028 KB Output is correct
26 Correct 1405 ms 14292 KB Output is correct
27 Correct 1454 ms 13628 KB Output is correct
28 Correct 770 ms 38920 KB Output is correct
29 Correct 1483 ms 48424 KB Output is correct
30 Correct 2055 ms 36752 KB Output is correct
31 Correct 1969 ms 29824 KB Output is correct
32 Correct 604 ms 10316 KB Output is correct
33 Correct 760 ms 10700 KB Output is correct
34 Correct 807 ms 42152 KB Output is correct
35 Correct 1068 ms 28492 KB Output is correct
36 Correct 2323 ms 46244 KB Output is correct
37 Correct 1868 ms 46508 KB Output is correct
38 Correct 1892 ms 45764 KB Output is correct
39 Correct 1556 ms 38120 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 939 ms 32216 KB Output is correct
13 Correct 728 ms 32340 KB Output is correct
14 Correct 986 ms 29260 KB Output is correct
15 Correct 1048 ms 29048 KB Output is correct
16 Correct 612 ms 15564 KB Output is correct
17 Correct 1044 ms 28940 KB Output is correct
18 Correct 1006 ms 28916 KB Output is correct
19 Correct 1101 ms 13436 KB Output is correct
20 Correct 1541 ms 7012 KB Output is correct
21 Correct 529 ms 1128 KB Output is correct
22 Correct 1652 ms 9580 KB Output is correct
23 Correct 626 ms 13736 KB Output is correct
24 Correct 821 ms 9548 KB Output is correct
25 Correct 1733 ms 13964 KB Output is correct
26 Correct 1500 ms 14292 KB Output is correct
27 Correct 1380 ms 13640 KB Output is correct
28 Correct 768 ms 38016 KB Output is correct
29 Correct 1496 ms 48292 KB Output is correct
30 Correct 2120 ms 36920 KB Output is correct
31 Correct 1972 ms 29816 KB Output is correct
32 Correct 605 ms 10184 KB Output is correct
33 Correct 728 ms 10812 KB Output is correct
34 Correct 802 ms 42112 KB Output is correct
35 Correct 1014 ms 28364 KB Output is correct
36 Correct 2173 ms 46112 KB Output is correct
37 Correct 1754 ms 46300 KB Output is correct
38 Correct 1688 ms 45732 KB Output is correct
39 Correct 1276 ms 87120 KB Output is correct
40 Correct 2616 ms 88140 KB Output is correct
41 Correct 3190 ms 70640 KB Output is correct
42 Correct 3000 ms 55100 KB Output is correct
43 Correct 1539 ms 82916 KB Output is correct
44 Correct 1006 ms 10692 KB Output is correct
45 Correct 1468 ms 38088 KB Output is correct
46 Correct 3291 ms 86840 KB Output is correct
47 Correct 3367 ms 86916 KB Output is correct
48 Correct 3160 ms 86400 KB Output is correct
49 Correct 1 ms 212 KB Output is correct