oj.uz

Submission #681898

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

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 16 ms 2644 KB Output is correct
8 Correct 17 ms 2700 KB Output is correct
9 Correct 18 ms 2660 KB Output is correct
10 Correct 18 ms 2692 KB Output is correct
11 Correct 17 ms 2692 KB Output is correct
12 Correct 21 ms 2668 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 16 ms 2644 KB Output is correct
8 Correct 17 ms 2700 KB Output is correct
9 Correct 18 ms 2660 KB Output is correct
10 Correct 18 ms 2692 KB Output is correct
11 Correct 17 ms 2692 KB Output is correct
12 Correct 21 ms 2668 KB Output is correct
13 Execution timed out 2104 ms 153272 KB Time limit exceeded
14 Halted 0 ms 0 KB -