oj.uz

Submission #681897

# Submission time Handle Problem Language Result Execution time Memory
681897 2023-01-14T18:52:43 Z four_specks Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 115400 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() : 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];

    SegmentTree st(n - 1, S(), op);
    for (int i = 0; i < n - 1; i++)
        st.set(i, d[i]);

    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 2 ms 340 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 21 ms 2156 KB Output is correct
8 Correct 21 ms 2136 KB Output is correct
9 Correct 21 ms 2148 KB Output is correct
10 Correct 22 ms 2144 KB Output is correct
11 Correct 24 ms 2152 KB Output is correct
12 Correct 21 ms 2152 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 21 ms 2156 KB Output is correct
8 Correct 21 ms 2136 KB Output is correct
9 Correct 21 ms 2148 KB Output is correct
10 Correct 22 ms 2144 KB Output is correct
11 Correct 24 ms 2152 KB Output is correct
12 Correct 21 ms 2152 KB Output is correct
13 Execution timed out 2067 ms 115400 KB Time limit exceeded
14 Halted 0 ms 0 KB -