Submission #1135977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135977		RandomUser	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	1 ms	320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct segment_tree {
    struct node {
        ll dp[2][2], b[2], _v;
        node(ll v = 0) {
            _v = v;
            dp[0][0] = dp[0][1] = dp[1][0] = 0;
            dp[1][1] = abs(v);
            b[0] = b[1] = (v < 0);
        }
    };

    node merge(node a, node b) {
        node res;
        for(int i=0; i<2; i++) {
            for(int j=0; j<2; j++) {
                for(int k=0; k<2; k++) {
                    for(int l=0; l<2; l++) {
                        if(j + k == 2 && a.b[1] == b.b[0]) res.dp[i][l] = max(res.dp[i][l], a.dp[i][j] + b.dp[k][l]);
                        else if(j != k) res.dp[i][l] = max(res.dp[i][l], a.dp[i][j] + b.dp[k][l]);
                    }
                }
            }
        }
        return res;
    }

    int n;
    vector<node> tree;

    segment_tree(int _n): n(_n), tree(4*n) {}

    void update(int u, int tl, int tr, int p, int v) {
        if(tl == tr) {
            tree[u] = node(tree[u]._v + v);
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) update(2*u, tl, tm, p, v);
            else update(2*u+1, tm+1, tr, p, v);
            tree[u] = merge(tree[2*u], tree[2*u+1]);
        }
    }

    void update(int p, int v) { update(1, 1, n, p, v); }

    ll query() {
        ll ans = 0;
        for(int i : { 0, 1 })
            for(int j : { 0, 1 }) ans = max(ans, tree[1].dp[i][j]);
        return ans;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, q; cin >> n >> q;
    vector<ll> a(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];

    segment_tree sgt(n-1);
    for(int i=1; i<n; i++) sgt.update(i, a[i+1] - a[i]);

    while(q--) {
        int l, r, x; cin >> l >> r >> x;
        if(l > 1) sgt.update(l-1, x);
        if(r < n) sgt.update(r, -x);
        cout << sgt.query() << '\n';
    }
}

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