Submission #1044841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044841		GasmaskChan	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	255 ms	26580 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int MAX = 2e5 + 5;

int d[MAX];
struct SMT {
    struct Node {
        int f[2][2];
        Node() {
            memset(f, 0, sizeof f);
        }
    };

    int n;
    vector<Node> ST;

    SMT(int _n) {
        n = _n;
        int sz = __lg(n) + 2;
        ST.resize(1 << sz);
    }

    void update(int id, int l, int r, const int &pos) {
        if (pos < l || r < pos) return;
        if (l == r) {
            ST[id].f[1][1] = abs(d[l]);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos);
        update(id << 1 | 1, mid + 1, r, pos);

        if ((d[mid] <= 0 && d[mid + 1] <= 0) || (d[mid] >= 0 && d[mid + 1] >= 0)) {
            ST[id].f[0][0] = max(ST[id << 1].f[0][1], ST[id << 1].f[0][0]) +
                             max(ST[id << 1 | 1].f[0][0], ST[id << 1 | 1].f[1][0]);
            ST[id].f[0][1] = max(ST[id << 1].f[0][0], ST[id << 1].f[0][1]) +
                             max(ST[id << 1 | 1].f[0][1], ST[id << 1 | 1].f[1][1]);
            ST[id].f[1][0] = max(ST[id << 1].f[1][0], ST[id << 1].f[1][1]) +
                             max(ST[id << 1 | 1].f[1][0], ST[id << 1 | 1].f[0][0]);
            ST[id].f[1][1] = max(ST[id << 1].f[1][0], ST[id << 1].f[1][1]) +
                             max(ST[id << 1 | 1].f[1][1], ST[id << 1 | 1].f[0][1]);
        }
        else {
            ST[id].f[0][0] = max(ST[id << 1].f[0][1] + ST[id << 1 | 1].f[0][0],
                                 ST[id << 1].f[0][0] + ST[id << 1 | 1].f[1][0]);
            ST[id].f[0][1] = max(ST[id << 1].f[0][0] + ST[id << 1 | 1].f[1][1],
                                 ST[id << 1].f[0][1] + ST[id << 1 | 1].f[0][1]);
            ST[id].f[1][0] = max(ST[id << 1].f[1][1] + ST[id << 1 | 1].f[0][0],
                                 ST[id << 1].f[1][0] + ST[id << 1 | 1].f[1][0]);
            ST[id].f[1][1] = max(ST[id << 1].f[1][1] + ST[id << 1 | 1].f[0][1],
                                 ST[id << 1].f[1][0] + ST[id << 1 | 1].f[1][1]);
        }
    }

    void update(const int &pos) {
        update(1, 1, n, pos);
    }

    int get() {
        return max({ST[1].f[0][0], ST[1].f[1][0], ST[1].f[0][1], ST[1].f[1][1]});
    }
};

int a[MAX];
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    SMT sech(n - 1);
    for (int i = 1; i < n; i++) {
        d[i] = a[i + 1] - a[i];
        sech.update(i);
    }

    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        d[l - 1] += x;
        d[r] -= x;
        if (l > 0) sech.update(l - 1);
        if (r < n) sech.update(r);
        cout << sech.get() << '\n';
    }
    return 0;
}

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