Submission #681898

#	Time	Username	Problem	Language	Result	Execution time	Memory
681898		four_specks	Sjeckanje (COCI21_sjeckanje)	C++17	55 / 110	2104 ms	153272 KiB

Main

#include <bits/stdc++.h>

using namespace std;

namespace
{
    template <typename T>
    int sgn(T x) { return (x > 0) - (x < 0); }

    template <typename T>
    bool ckmin(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }

    template <typename T>
    bool ckmax(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

    template <typename S, typename Op>
    struct SegmentTree
    {
        SegmentTree(int _n, S _e = S(), Op _op = Op())
            : n(1 << (__lg(2 * _n - 1))), e(_e), op(_op), tree(2 * n, e)
        {
        }

        SegmentTree(const vector<S> &vec, S _e = S(), Op _op = Op())
            : SegmentTree((int)vec.size(), _e, _op)
        {
            for (int p = 0; p < (int)vec.size(); p++)
                tree[p + n] = vec[p];
            for (int p = n - 1; p; p--)
                tree[p] = op(tree[p * 2], tree[p * 2 + 1]);
        }

        void set(int p, S x)
        {
            int k = p + n;

            tree[k] = x;
            while (k /= 2)
                tree[k] = op(tree[k * 2], tree[k * 2 + 1]);
        }

        S get(int p) const { return tree[p + n]; }

        S query(int l, int r) const
        {
            S ra = e, rb = e;
            for (int a = l + n, b = r + n; a < b; a /= 2, b /= 2)
            {
                if (a % 2)
                    ra = op(ra, tree[a++]);
                if (b % 2)
                    rb = op(tree[--b], rb);
            }

            return op(ra, rb);
        }

        S query() const { return tree[1]; }

        int size() const { return n; }

    private:
        int n;
        S e;
        Op op;

        vector<S> tree;
    };

} // namespace

struct S
{
    S() : bord(2), seg(2, vector<long>(2, -1)) {}

    S(long x)
        : S()
    {
        bord[0] = bord[1] = sgn(x);
        seg[0][0] = seg[0][1] = seg[1][0] = 0;
        seg[1][1] = abs(x);
    }

    vector<int> bord;
    vector<vector<long>> seg;
};

S op(const S &x, const S &y)
{
    if (x.seg[0][0] == -1)
        return y;
    if (y.seg[0][0] == -1)
        return x;

    S z;

    z.bord[0] = x.bord[0];
    z.bord[1] = y.bord[1];

    if (x.bord[1] * y.bord[0] == -1)
    {
        for (int p : {0, 1})
        {
            for (int q : {0, 1})
                z.seg[p][q] = max(x.seg[p][0] + y.seg[1][q], x.seg[p][1] + y.seg[0][q]);
        }
    }
    else
    {
        for (int p : {0, 1})
        {
            for (int q : {0, 1})
                z.seg[p][q] = x.seg[p][1] + y.seg[1][q];
        }
    }

    return z;
}

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

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

    vector<long> d(n - 1);
    for (int i = 0; i < n - 1; i++)
        d[i] = a[i] - a[i + 1];

    vector<S> v(n - 1);
    for (int i = 0; i < n - 1; i++)
        v[i] = S(d[i]);

    SegmentTree st(v, S(), op);

    for (int c = 0; c < q; c++)
    {
        int l, r;
        long x;
        cin >> l >> r >> x, --l;

        if (l > 0)
        {
            d[l - 1] -= x;
            st.set(l - 1, d[l - 1]);
        }
        if (r < n)
        {
            d[r - 1] += x;
            st.set(r - 1, d[r - 1]);
        }

        long res = st.query().seg[1][1];

        cout << res << '\n';
    }
}

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

    solve();

    return 0;
}

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