oj.uz

Submission #736486

# Submission time Handle Problem Language Result Execution time Memory
736486 2023-05-05T18:12:12 Z four_specks Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 259 ms 10192 KB 
#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename Fun>
    struct YCombinator
    {
        template <typename T>
        YCombinator(T &&_fun) : fun(forward<T>(_fun)) {}

        template <typename... Args>
        decltype(auto) operator()(Args &&...args) { return fun(ref(*this), forward<Args>(args)...); }

    private:
        Fun fun;
    };

    template <typename T>
    YCombinator(T &&) -> YCombinator<decay_t<T>>;

} // namespace

void solve()
{
    int n, q;
    long d;
    cin >> n >> q >> d;

    vector<long> a(n);
    for (long &x : a)
        cin >> x;

    struct Node
    {
        int l, r;
        long sum, ma;
    };

    int m = 1 << __lg(2 * n - 1);

    vector<Node> nodes(2 * m);

    auto pull_node = [&](int p) -> void
    {
        Node &nod = nodes[p], &lft = nodes[p * 2], &rgt = nodes[p * 2 + 1];

        nod.sum = lft.sum + rgt.sum;
        nod.ma = max(lft.ma, rgt.ma);
    };

    YCombinator set_node = [&](auto self, int p, int j, long x) -> void
    {
        Node &nod = nodes[p];

        if (j < nod.l || nod.r <= j)
            return;

        if (nod.r - nod.l == 1)
        {
            nod.ma = nod.sum = x;

            return;
        }

        self(p * 2, j, x);
        self(p * 2 + 1, j, x);

        pull_node(p);
    };

    YCombinator upd_node = [&](auto self, int p, int l, int r) -> void
    {
        Node &nod = nodes[p];

        if (r <= nod.l || nod.r <= l || nod.ma == 0)
            return;

        if (nod.r - nod.l == 1)
        {
            nod.sum /= d;
            nod.ma = nod.sum;

            return;
        }

        self(p * 2, l, r);
        self(p * 2 + 1, l, r);

        pull_node(p);
    };

    YCombinator qry_node = [&](auto self, int p, int l, int r) -> long
    {
        Node &nod = nodes[p];

        if (r <= nod.l || nod.r <= l)
            return 0;

        if (l <= nod.l && nod.r <= r)
            return nod.sum;

        return self(p * 2, l, r) + self(p * 2 + 1, l, r);
    };

    YCombinator(
        [&](auto self, int p, int l, int r) -> void
        {
            Node &nod = nodes[p];

            nod.l = l;
            nod.r = r;

            if (r - l == 1)
            {
                nod.ma = nod.sum = (l < n ? a[l] : 0);

                return;
            }

            int mid = (l + r) / 2;

            self(p * 2, l, mid);
            self(p * 2 + 1, mid, r);

            pull_node(p);
        })(1, 0, m);

    for (int i = 0; i < q; i++)
    {
        int t;
        cin >> t;

        if (t == 1)
        {
            int j;
            long x;
            cin >> j >> x, --j;

            set_node(1, j, x);
        }
        else if (t == 2)
        {
            int l, r;
            cin >> l >> r, --l;

            if (d > 1)
                upd_node(1, l, r);
        }
        else if (t == 3)
        {
            int l, r;
            cin >> l >> r, --l;

            cout << qry_node(1, l, r) << '\n';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 4 ms 584 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 5 ms 616 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 6 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6084 KB Output is correct
2 Correct 49 ms 5656 KB Output is correct
3 Correct 47 ms 8968 KB Output is correct
4 Correct 59 ms 9660 KB Output is correct
5 Correct 72 ms 10068 KB Output is correct
6 Correct 74 ms 10128 KB Output is correct
7 Correct 72 ms 10180 KB Output is correct
8 Correct 70 ms 10104 KB Output is correct
9 Correct 63 ms 9960 KB Output is correct
10 Correct 59 ms 10044 KB Output is correct
11 Correct 81 ms 10040 KB Output is correct
12 Correct 63 ms 10056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1156 KB Output is correct
2 Correct 14 ms 4040 KB Output is correct
3 Correct 20 ms 4140 KB Output is correct
4 Correct 66 ms 3240 KB Output is correct
5 Correct 72 ms 8692 KB Output is correct
6 Correct 65 ms 8672 KB Output is correct
7 Correct 60 ms 8812 KB Output is correct
8 Correct 66 ms 8700 KB Output is correct
9 Correct 60 ms 8548 KB Output is correct
10 Correct 62 ms 8560 KB Output is correct
11 Correct 60 ms 8652 KB Output is correct
12 Correct 58 ms 8524 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 5456 KB Output is correct
2 Correct 105 ms 5708 KB Output is correct
3 Correct 126 ms 4952 KB Output is correct
4 Correct 131 ms 3976 KB Output is correct
5 Correct 152 ms 9920 KB Output is correct
6 Correct 167 ms 10028 KB Output is correct
7 Correct 150 ms 9948 KB Output is correct
8 Correct 200 ms 10192 KB Output is correct
9 Correct 173 ms 9892 KB Output is correct
10 Correct 200 ms 9948 KB Output is correct
11 Correct 140 ms 9816 KB Output is correct
12 Correct 259 ms 9832 KB Output is correct