Submission #736486

#	Time	Username	Problem	Language	Result	Execution time	Memory
736486		four_specks	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	259 ms	10192 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75