Submission #680855

#	Time	Username	Problem	Language	Result	Execution time	Memory
680855		finn__	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	754 ms	28992 KiB

Main

#include <bits/stdc++.h>
using namespace std;

bool sign(int64_t x)
{
    return x > 0;
}

struct segtree
{
    vector<array<int64_t, 4>> t;
    vector<array<bool, 2>> y;
    size_t l;

    void transition(size_t i)
    {
        y[i][0] = y[2 * i][0];
        y[i][1] = y[2 * i + 1][1];

        for (size_t j = 0; j < 4; j++)
        {
            int64_t const a1 = t[2 * i][j & 1], a2 = t[2 * i][(j & 1) + 2],
                          b1 = t[2 * i + 1][j & 2], b2 = t[2 * i + 1][(j & 2) + 1];

            t[i][j] = max(a1 + b1, max(a1 + b2, a2 + b1));
            if (y[2 * i][1] == y[2 * i + 1][0])
                t[i][j] = max(t[i][j], a2 + b2);
        }
    }

    segtree(vector<int64_t> const &a)
    {
        l = 1 << (32 - __builtin_clz(a.size() - 1));
        t = vector<array<int64_t, 4>>(2 * l, {0, 0, 0, 0});
        y = vector<array<bool, 2>>(2 * l);

        for (size_t i = 0; i < a.size() - 1; i++)
        {
            t[l + i] = {0, 0, 0, abs(a[i + 1] - a[i])};
            y[l + i][0] = y[l + i][1] = sign(a[i + 1] - a[i]);
        }

        for (size_t i = a.size() - 1; i < l; i++)
            y[l + i][0] = y[l + i][1] = y[l + a.size() - 2][0];

        for (size_t i = l - 1; i; i--)
            transition(i);
    }

    void update(size_t i, int64_t x)
    {
        i += l;

        t[i][3] += y[i][0] ? x : -x;
        if (t[i][3] < 0)
        {
            y[i][0] = y[i][1] = !y[i][0];
            t[i][3] = -t[i][3];
        }

        while (i > 1)
        {
            i >>= 1;
            transition(i);
        }
    }

    int64_t max_value()
    {
        return max(max(t[1][0], t[1][1]), max(t[1][2], t[1][3]));
    }
};

int main()
{
    size_t n, q;
    cin >> n >> q;

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

    segtree tree(a);

    for (size_t i = 0; i < q; i++)
    {
        size_t l, r;
        int64_t x;
        cin >> l >> r >> x;
        if (l > 1)
            tree.update(l - 2, x);
        if (r < n)
            tree.update(r - 1, -x);
        cout << tree.max_value() << '\n';
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55