Submission #1207920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207920		teslerpham	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	464 ms	37828 KiB

Main

/*
   Sjeckanje  –  COI 2021 R5
   -------------------------------------------------
   Maximum value after range-add updates.

   Key facts
   ----------
   *  Let d[i] = a[i+1] – a[i]  (1 ≤ i ≤ n-1).
   *  Best chopping value = Σ |d[i]|  minus those |d[i]| that we
      decide to “cut away”.
   *  Two consecutive differences of *opposite* sign may **not**
      be kept simultaneously (otherwise the segment would
      contain both an up-step and a down-step → not monotone).

   ↳  Choose a subset of indices that maximises
      Σ |d[i]| subject to:
        if we keep d[i] and d[i+1] then  sign(d[i])·sign(d[i+1]) ≠ −1

   We maintain a segment tree.  
   Each node keeps the best sum for the four possibilities
   (keep / drop the first diff, keep / drop the last diff).

   Node fields
   -----------
   - val[2][2] :  maximum sum for
                 val[lf][rg] where
                   lf = 1 if the first diff of the segment is kept
                   rg = 1 if the last  diff of the segment is kept
   - sL, sR    :  sign of first / last diff in the segment
                  (-1, 0, +1)

   Merge rule
   ----------
   For every combination of (lf1, rg1) from left child
   and (lf2, rg2) from right child:

        * invalid if  rg1 = 1  &&  lf2 = 1
                      && signs are opposite (+1 vs −1)

        * otherwise  new-left  = lf1
                     new-right = rg2
                     val = sum of the two children

   Complexity
   ----------
   Build :  O(n)
   Update:  O(log n)   (only two point updates per query)
   Answer :  O(1)

   -------------------------------------------------
*/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = -(1LL << 60);

struct Node {
    ll val[2][2];          // val[keepLeft][keepRight]
    int sL, sR;            // sign of first / last diff

    Node() {
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                val[i][j] = NEG_INF;
        sL = sR = 0;
    }
};

inline int sgn(ll x) { return (x > 0) - (x < 0); }

Node merge(const Node& A, const Node& B) {
    if (A.val[0][0] == NEG_INF) return B;
    if (B.val[0][0] == NEG_INF) return A;

    Node C;
    C.sL = A.sL;
    C.sR = B.sR;

    for (int al = 0; al <= 1; ++al)
        for (int ar = 0; ar <= 1; ++ar)
            if (A.val[al][ar] != NEG_INF)
                for (int bl = 0; bl <= 1; ++bl)
                    for (int br = 0; br <= 1; ++br)
                        if (B.val[bl][br] != NEG_INF) {
                            if (ar && bl) {
                                // two consecutive kept diffs – must not have opposite signs
                                int s1 = A.sR, s2 = B.sL;
                                if (s1 != 0 && s2 != 0 && s1 != s2) continue;
                            }
                            ll cand = A.val[al][ar] + B.val[bl][br];
                            int nl = al;
                            int nr = br;
                            C.val[nl][nr] = max(C.val[nl][nr], cand);
                        }
    return C;
}

struct SegTree {
    int n;                   // number of diffs (n = N-1)
    vector<Node> st;         // 4*n
    SegTree(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        st.assign(4 * max(1, n), Node());
    }

    Node make_leaf(ll diff) {
        Node nd;
        nd.sL = nd.sR = sgn(diff);
        nd.val[0][0] = 0;
        nd.val[1][1] = llabs(diff);        // keeping the only diff
        // impossible mixed states stay NEG_INF
        return nd;
    }

    void build(int p, int l, int r, const vector<ll>& diff) {
        if (l == r) {
            st[p] = make_leaf(diff[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid, diff);
        build(p << 1 | 1, mid + 1, r, diff);
        st[p] = merge(st[p << 1], st[p << 1 | 1]);
    }

    void build(const vector<ll>& diff) {             // diff is 1-based of size n
        if (n == 0) return;
        build(1, 1, n, diff);
    }

    // point update: position idx gets new diff value 'val'
    void update(int p, int l, int r, int idx, ll val) {
        if (l == r) {
            st[p] = make_leaf(val);
            return;
        }
        int mid = (l + r) >> 1;
        if (idx <= mid) update(p << 1, l, mid, idx, val);
        else            update(p << 1 | 1, mid + 1, r, idx, val);
        st[p] = merge(st[p << 1], st[p << 1 | 1]);
    }
    void update(int idx, ll val) {                    // idx is 1-based in diff array
        if (n == 0) return;
        update(1, 1, n, idx, val);
    }

    ll best() const {
        if (n == 0) return 0LL;
        const Node& rt = st[1];
        ll ans = 0;
        for (int i = 0; i <= 1; ++i)
            for (int j = 0; j <= 1; ++j)
                ans = max(ans, rt.val[i][j]);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;
    vector<ll> a(N + 1);
    for (int i = 1; i <= N; ++i) cin >> a[i];

    int M = max(0, N - 1);            // number of diffs
    vector<ll> diff(M + 1);           // 1-based
    for (int i = 1; i <= M; ++i) diff[i] = a[i + 1] - a[i];

    SegTree seg(M);
    if (M) seg.build(diff);

    while (Q--) {
        int l, r;
        ll x;
        cin >> l >> r >> x;

        if (l > 1) {
            int idx = l - 1;
            diff[idx] += x;           // d[l-1] increases by x
            seg.update(idx, diff[idx]);
        }
        if (r < N) {
            int idx = r;
            diff[idx] -= x;           // d[r] decreases by x
            seg.update(idx, diff[idx]);
        }
        cout << seg.best() << '\n';
    }
    return 0;
}

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