oj.uz

Submission #681900

# Submission time Handle Problem Language Result Execution time Memory
681900 2023-01-14T18:57:29 Z four_specks Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 332 ms 41428 KB 
#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() { seg[0][0] = -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);
    }

    array<int, 2> bord;
    array<array<long, 2>, 2> 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 3 ms 852 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 316 ms 36164 KB Output is correct
14 Correct 324 ms 40844 KB Output is correct
15 Correct 321 ms 40912 KB Output is correct
16 Correct 332 ms 40780 KB Output is correct
17 Correct 314 ms 40776 KB Output is correct
18 Correct 301 ms 41428 KB Output is correct