oj.uz

Submission #414845

# Submission time Handle Problem Language Result Execution time Memory
414845 2021-05-31T09:05:35 Z KoD Game (IOI13_game) C++17
100 / 100
 8599 ms 54124 KB 
#include <bits/stdc++.h>
#include "game.h"

using ll = long long;
using ull = unsigned long long;

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

ull xorshift() {
    static ull val = 7511168;
    val ^= val >> 7;
    val ^= val << 9;
    return val;
}

struct Node;
using Ptr = Box<Node>;

struct Node {
    int pos, size;
    ull val, gcd;
    Ptr left, right;
    Node(const int p, const ull v): pos(p), size(1), val(v), gcd(v), left(), right() {}
    void fetch() {
        size = (left ? left->size : 0) + 1 + (right ? right->size : 0);
        gcd = val;
        if (left) gcd = std::gcd(gcd, left->gcd);
        if (right) gcd = std::gcd(gcd, right->gcd);
    }
};

Ptr merge(Ptr x, Ptr y) {
    if (!x) return y;
    if (!y) return x;
    if (xorshift() % (x->size + y->size) < x->size) {
        x->right = merge(std::move(x->right), std::move(y));
        x->fetch();
        return x;
    } else {
        y->left = merge(std::move(x), std::move(y->left));
        y->fetch();
        return y;
    }
}

std::pair<Ptr, Ptr> split(Ptr x, const int p) {
    if (!x) return {Ptr(), Ptr()};
    if (x->pos >= p) {
        auto [l, r] = split(std::move(x->left), p);
        x->left = std::move(r);
        x->fetch();
        return {std::move(l), std::move(x)};
    } else {
        auto [l, r] = split(std::move(x->right), p);
        x->right = std::move(l);
        x->fetch();
        return {std::move(x), std::move(r)};
    }
}

void set(Ptr& x, const int p, const ull v) {
    auto [l, s] = split(std::move(x), p);
    auto [t, r] = split(std::move(s), p + 1);
    x = merge(merge(std::move(l), std::make_unique<Node>(p, v)), std::move(r));
}

ull gcd(Ptr& x, const int a, const int b) {
    auto [l, s] = split(std::move(x), a);
    auto [t, r] = split(std::move(s), b);
    const auto ret = (t ? t->gcd : 0);
    x = merge(merge(std::move(l), std::move(t)), std::move(r));
    return ret;
}

ull gcd(Ptr& x, const int p) {
    if (!x) return 0;
    if (x->pos > p) return gcd(x->left, p);
    if (x->pos < p) return gcd(x->right, p);
    return x->val;
}

struct Segtree {
    struct Data {
        int left, right, lch, rch;
        Ptr tree;
        Data(const int l, const int r): left(l), right(r), lch(-1), rch(-1), tree() {}
    };
    Vec<Data> data;
    Segtree() = default;
    Segtree(const int row) {
        data.emplace_back(0, row);
    }
    void assign(const int x, const int y, const ull v) {
        int u = 0;
        Vec<int> path;
        while (data[u].right - data[u].left > 1) {
            path.push_back(u);
            const int mid = (data[u].left + data[u].right) / 2;
            if (x < mid) {
                if (data[u].lch == -1) {
                    data.emplace_back(data[u].left, mid);
                    data[u].lch = (int) data.size() - 1;
                }
                u = data[u].lch;
            }
            else {
                if (data[u].rch == -1) {
                    data.emplace_back(mid, data[u].right);
                    data[u].rch = (int) data.size() - 1;
                }
                u = data[u].rch;
            }
        }
        set(data[u].tree, y, v);
        while (!path.empty()) {
            u = path.back();
            path.pop_back();
            const int l = data[u].lch;
            const int r = data[u].rch;
            set(data[u].tree, y, std::gcd(l == -1 ? 0 : gcd(data[l].tree, y), r == -1 ? 0 : gcd(data[r].tree, y)));
        }
    }
    void fold(const int l, const int r, const int l2, const int r2, ull& ret, const int u = 0) {
        if (u == -1 or r <= data[u].left or data[u].right <= l) return;
        if (l <= data[u].left and data[u].right <= r) {
            ret = std::gcd(ret, gcd(data[u].tree, l2, r2));
            return;
        }
        fold(l, r, l2, r2, ret, data[u].lch);
        fold(l, r, l2, r2, ret, data[u].rch);
    }
};

Segtree seg;

void init(int R, int C) {
    seg = Segtree(R);
}

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

ll calculate(int P, int Q, int U, int V) {
    ull ret = 0;
    seg.fold(P, U + 1, Q, V + 1, ret);
    return ret;
}

Compilation message

game.cpp: In function 'Ptr merge(Ptr, Ptr)':
game.cpp:36:42: warning: comparison of integer expressions of different signedness: 'ull' {aka 'long long unsigned int'} and 'int' [-Wsign-compare]
   36 |     if (xorshift() % (x->size + y->size) < x->size) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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 332 KB Output is correct
5 Correct 1 ms 288 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 204 KB Output is correct
11 Correct 1 ms 204 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 296 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1666 ms 10740 KB Output is correct
5 Correct 704 ms 10512 KB Output is correct
6 Correct 1605 ms 8032 KB Output is correct
7 Correct 1869 ms 7820 KB Output is correct
8 Correct 1223 ms 7092 KB Output is correct
9 Correct 1769 ms 7940 KB Output is correct
10 Correct 1700 ms 7460 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 448 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 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 292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2638 ms 12232 KB Output is correct
13 Correct 4864 ms 6932 KB Output is correct
14 Correct 590 ms 5640 KB Output is correct
15 Correct 5138 ms 8092 KB Output is correct
16 Correct 456 ms 9856 KB Output is correct
17 Correct 2456 ms 8860 KB Output is correct
18 Correct 4098 ms 11260 KB Output is correct
19 Correct 3520 ms 11344 KB Output is correct
20 Correct 3539 ms 10728 KB Output is correct
21 Correct 1 ms 204 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 332 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 288 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 2 ms 292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1682 ms 10636 KB Output is correct
13 Correct 665 ms 10560 KB Output is correct
14 Correct 1623 ms 8044 KB Output is correct
15 Correct 1852 ms 7728 KB Output is correct
16 Correct 1240 ms 7204 KB Output is correct
17 Correct 1789 ms 7804 KB Output is correct
18 Correct 1715 ms 7460 KB Output is correct
19 Correct 2676 ms 12128 KB Output is correct
20 Correct 4855 ms 7116 KB Output is correct
21 Correct 590 ms 5564 KB Output is correct
22 Correct 5211 ms 8104 KB Output is correct
23 Correct 465 ms 9744 KB Output is correct
24 Correct 2456 ms 8924 KB Output is correct
25 Correct 4117 ms 11128 KB Output is correct
26 Correct 3631 ms 11472 KB Output is correct
27 Correct 3581 ms 10700 KB Output is correct
28 Correct 1345 ms 30064 KB Output is correct
29 Correct 3454 ms 32640 KB Output is correct
30 Correct 6181 ms 23500 KB Output is correct
31 Correct 5499 ms 19616 KB Output is correct
32 Correct 764 ms 10132 KB Output is correct
33 Correct 1226 ms 10452 KB Output is correct
34 Correct 711 ms 26376 KB Output is correct
35 Correct 2835 ms 20744 KB Output is correct
36 Correct 5489 ms 30688 KB Output is correct
37 Correct 4415 ms 30768 KB Output is correct
38 Correct 4493 ms 30200 KB Output is correct
39 Correct 3606 ms 27816 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 2 ms 288 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1676 ms 10768 KB Output is correct
13 Correct 657 ms 10664 KB Output is correct
14 Correct 1600 ms 8008 KB Output is correct
15 Correct 1870 ms 7832 KB Output is correct
16 Correct 1230 ms 7040 KB Output is correct
17 Correct 1752 ms 7728 KB Output is correct
18 Correct 1649 ms 7368 KB Output is correct
19 Correct 2616 ms 12092 KB Output is correct
20 Correct 4803 ms 7036 KB Output is correct
21 Correct 590 ms 5592 KB Output is correct
22 Correct 5187 ms 7996 KB Output is correct
23 Correct 451 ms 9784 KB Output is correct
24 Correct 2518 ms 8848 KB Output is correct
25 Correct 4198 ms 11348 KB Output is correct
26 Correct 3521 ms 11372 KB Output is correct
27 Correct 3571 ms 11032 KB Output is correct
28 Correct 1375 ms 30196 KB Output is correct
29 Correct 3544 ms 32996 KB Output is correct
30 Correct 6235 ms 23260 KB Output is correct
31 Correct 5518 ms 19824 KB Output is correct
32 Correct 751 ms 10128 KB Output is correct
33 Correct 1211 ms 10484 KB Output is correct
34 Correct 699 ms 26532 KB Output is correct
35 Correct 2859 ms 20972 KB Output is correct
36 Correct 5509 ms 30760 KB Output is correct
37 Correct 4321 ms 30848 KB Output is correct
38 Correct 4390 ms 30172 KB Output is correct
39 Correct 1857 ms 52104 KB Output is correct
40 Correct 5489 ms 54124 KB Output is correct
41 Correct 8599 ms 41276 KB Output is correct
42 Correct 7895 ms 33240 KB Output is correct
43 Correct 1176 ms 48980 KB Output is correct
44 Correct 1085 ms 10540 KB Output is correct
45 Correct 3654 ms 28072 KB Output is correct
46 Correct 6756 ms 52940 KB Output is correct
47 Correct 6765 ms 53000 KB Output is correct
48 Correct 7171 ms 52572 KB Output is correct
49 Correct 1 ms 204 KB Output is correct