oj.uz

Submission #413588

# Submission time Handle Problem Language Result Execution time Memory
413588 2021-05-29T02:16:38 Z KoD Game (IOI13_game) C++17
80 / 100
 3874 ms 256004 KB 
#include <bits/stdc++.h>
#include "game.h"

using ll = long long;

template <class T> using Vec = std::vector<T>;

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

namespace solver {

int Row, Column;

struct SegGCD {
    struct Node {
        ll gcd;
        int left, right;
        std::array<int, 2> ch;
        Node(const int left, const int right): gcd(0), left(left), right(right), ch({-1, -1}) {}
    };

    Vec<Node> node;

    SegGCD() {
        node.emplace_back(0, Column);
    }

    void fetch(const int u) {
        const int l = node[u].ch[0];
        const int r = node[u].ch[1];
        node[u].gcd = gcd2(l == -1 ? 0 : node[l].gcd, r == -1 ? 0 : node[r].gcd);
    }

    void assign(const int x, const ll v) {
        int u = 0;
        Vec<int> path;
        while (node[u].right - node[u].left > 1) {
            path.push_back(u);
            const int mid = (node[u].left + node[u].right) / 2;
            if (x < mid) {
                if (node[u].ch[0] == -1) {
                    node.emplace_back(node[u].left, mid);
                    node[u].ch[0] = (int) node.size() - 1;
                }
                u = node[u].ch[0];
            }
            else {
                if (node[u].ch[1] == -1) {
                    node.emplace_back(mid, node[u].right);
                    node[u].ch[1] = (int) node.size() - 1;
                }
                u = node[u].ch[1];
            }
        }
        node[u].gcd = v;
        while (!path.empty()) {
            fetch(path.back());
            path.pop_back();
        }
    }

    void fold(const int u, const int l, const int r, ll& base) {
        if (u == -1 or node[u].right <= l or r <= node[u].left) {
            return;
        }
        if (l <= node[u].left and node[u].right <= r) {
            base = gcd2(base, node[u].gcd);
            return;
        }
        fold(node[u].ch[0], l, r, base);
        fold(node[u].ch[1], l, r, base);
    }
};

struct Seg2D {
    struct Node {
        SegGCD seg;
        int left, right;
        std::array<int, 2> ch;
        Node(const int left, const int right) : seg(), left(left), right(right), ch({-1, -1}) {}
    };
    
    Vec<Node> node;

    Seg2D() {
        node.emplace_back(0, Row);
    }

    void assign(const int x, const int y, const ll v) {
        int u = 0;
        Vec<int> path;
        while (node[u].right - node[u].left > 1) {
            path.push_back(u);
            const int mid = (node[u].left + node[u].right) / 2;
            if (x < mid) {
                if (node[u].ch[0] == -1) {
                    node.emplace_back(node[u].left, mid);
                    node[u].ch[0] = (int) node.size() - 1;
                }
                u = node[u].ch[0];
            }
            else {
                if (node[u].ch[1] == -1) {
                    node.emplace_back(mid, node[u].right);
                    node[u].ch[1] = (int) node.size() - 1;
                }
                u = node[u].ch[1];
            }
        }
        node[u].seg.assign(y, v);
        while (!path.empty()) {
            u = path.back();
            path.pop_back();
            const int l = node[u].ch[0];
            const int r = node[u].ch[1];
            ll g = 0;
            if (l != -1) {
                node[l].seg.fold(0, y, y + 1, g);
            }
            if (r != -1) {
                node[r].seg.fold(0, y, y + 1, g);
            }
            node[u].seg.assign(y, g);
        }
    }

    void fold(const int u, const int l, const int r, const int l2, const int r2, ll& base) {
        if (u == -1 or node[u].right <= l or r <= node[u].left) {
            return;
        }
        if (l <= node[u].left and node[u].right <= r) {
            node[u].seg.fold(0, l2, r2, base);
            return;
        }
        fold(node[u].ch[0], l, r, l2, r2, base);
        fold(node[u].ch[1], l, r, l2, r2, base);
    }
};

Seg2D seg;

}

void init(int R, int C) {
    using namespace solver;
    Row = R;
    Column = C;
    seg = Seg2D();
}

void update(int P, int Q, ll K) {
    using namespace solver;
    seg.assign(P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    using namespace solver;
    ll base = 0;
    seg.fold(0, P, U + 1, Q, V + 1, base);
    return base;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 684 ms 16752 KB Output is correct
5 Correct 441 ms 16704 KB Output is correct
6 Correct 490 ms 14312 KB Output is correct
7 Correct 567 ms 13812 KB Output is correct
8 Correct 366 ms 11000 KB Output is correct
9 Correct 550 ms 13800 KB Output is correct
10 Correct 513 ms 13096 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 424 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 296 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1016 ms 20716 KB Output is correct
13 Correct 1436 ms 10500 KB Output is correct
14 Correct 352 ms 5668 KB Output is correct
15 Correct 1780 ms 13264 KB Output is correct
16 Correct 290 ms 23536 KB Output is correct
17 Correct 809 ms 17088 KB Output is correct
18 Correct 1260 ms 25020 KB Output is correct
19 Correct 1152 ms 25184 KB Output is correct
20 Correct 1101 ms 24468 KB Output is correct
21 Correct 1 ms 292 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 612 ms 16624 KB Output is correct
13 Correct 431 ms 16756 KB Output is correct
14 Correct 533 ms 14220 KB Output is correct
15 Correct 508 ms 13924 KB Output is correct
16 Correct 396 ms 11040 KB Output is correct
17 Correct 532 ms 13864 KB Output is correct
18 Correct 572 ms 13232 KB Output is correct
19 Correct 1022 ms 20812 KB Output is correct
20 Correct 1461 ms 10340 KB Output is correct
21 Correct 323 ms 5536 KB Output is correct
22 Correct 1705 ms 13172 KB Output is correct
23 Correct 281 ms 23496 KB Output is correct
24 Correct 792 ms 17216 KB Output is correct
25 Correct 1330 ms 24920 KB Output is correct
26 Correct 1173 ms 25104 KB Output is correct
27 Correct 1125 ms 24496 KB Output is correct
28 Correct 942 ms 226712 KB Output is correct
29 Correct 2164 ms 248020 KB Output is correct
30 Correct 3835 ms 180716 KB Output is correct
31 Correct 3657 ms 146940 KB Output is correct
32 Correct 623 ms 10536 KB Output is correct
33 Correct 847 ms 14008 KB Output is correct
34 Correct 766 ms 242564 KB Output is correct
35 Correct 1374 ms 129252 KB Output is correct
36 Correct 2575 ms 246328 KB Output is correct
37 Correct 2199 ms 246340 KB Output is correct
38 Correct 2207 ms 246020 KB Output is correct
39 Correct 1844 ms 192024 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 605 ms 16776 KB Output is correct
13 Correct 430 ms 16700 KB Output is correct
14 Correct 511 ms 14272 KB Output is correct
15 Correct 513 ms 14072 KB Output is correct
16 Correct 406 ms 10996 KB Output is correct
17 Correct 509 ms 13800 KB Output is correct
18 Correct 470 ms 13140 KB Output is correct
19 Correct 1073 ms 20868 KB Output is correct
20 Correct 1518 ms 10296 KB Output is correct
21 Correct 338 ms 5572 KB Output is correct
22 Correct 1697 ms 13236 KB Output is correct
23 Correct 285 ms 23512 KB Output is correct
24 Correct 790 ms 17216 KB Output is correct
25 Correct 1322 ms 24972 KB Output is correct
26 Correct 1133 ms 25008 KB Output is correct
27 Correct 1083 ms 24464 KB Output is correct
28 Correct 999 ms 226716 KB Output is correct
29 Correct 2159 ms 248020 KB Output is correct
30 Correct 3874 ms 180676 KB Output is correct
31 Correct 3703 ms 146944 KB Output is correct
32 Correct 614 ms 10472 KB Output is correct
33 Correct 842 ms 13900 KB Output is correct
34 Correct 805 ms 242328 KB Output is correct
35 Correct 1354 ms 129380 KB Output is correct
36 Correct 2618 ms 246104 KB Output is correct
37 Correct 2217 ms 246284 KB Output is correct
38 Correct 2254 ms 245984 KB Output is correct
39 Runtime error 794 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -