Submission #1205360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205360		takoshanava	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	349 ms	31088 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 200005;

int n, q;
int a[N], d[N];
int dp[N * 4][2][2], head[N * 4], tail[N * 4];

void build(int id, int l, int r) {
    if (l == r) {
        int val = d[l];
        dp[id][0][0] = dp[id][0][1] = dp[id][1][0] = 0;
        dp[id][1][1] = abs(val);
        head[id] = tail[id] = val;
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);

    int lch = id * 2, rch = id * 2 + 1;

    if (tail[lch] * head[rch] < 0) {
        dp[id][0][0] = max(dp[lch][0][1] + dp[rch][0][0], dp[lch][0][0] + dp[rch][1][0]);
        dp[id][0][1] = max(dp[lch][0][1] + dp[rch][0][1], dp[lch][0][0] + dp[rch][1][1]);
        dp[id][1][0] = max(dp[lch][1][1] + dp[rch][0][0], dp[lch][1][0] + dp[rch][1][0]);
        dp[id][1][1] = max(dp[lch][1][1] + dp[rch][0][1], dp[lch][1][0] + dp[rch][1][1]);
    } else {
        dp[id][0][0] = dp[lch][0][1] + dp[rch][1][0];
        dp[id][0][1] = dp[lch][0][1] + dp[rch][1][1];
        dp[id][1][0] = dp[lch][1][1] + dp[rch][1][0];
        dp[id][1][1] = dp[lch][1][1] + dp[rch][1][1];
    }
    head[id] = head[lch];
    tail[id] = tail[rch];
}

void upd(int id, int l, int r, int pos, int val) {
    if (l > pos || r < pos) return;
    if (l == r) {
        d[l] += val;
        dp[id][0][0] = dp[id][0][1] = dp[id][1][0] = 0;
        dp[id][1][1] = abs(d[l]);
        head[id] = tail[id] = d[l];
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) upd(id * 2, l, mid, pos, val);
    else upd(id * 2 + 1, mid + 1, r, pos, val);

    int lch = id * 2, rch = id * 2 + 1;

    if (tail[lch] * head[rch] < 0) {
        dp[id][0][0] = max(dp[lch][0][1] + dp[rch][0][0], dp[lch][0][0] + dp[rch][1][0]);
        dp[id][0][1] = max(dp[lch][0][1] + dp[rch][0][1], dp[lch][0][0] + dp[rch][1][1]);
        dp[id][1][0] = max(dp[lch][1][1] + dp[rch][0][0], dp[lch][1][0] + dp[rch][1][0]);
        dp[id][1][1] = max(dp[lch][1][1] + dp[rch][0][1], dp[lch][1][0] + dp[rch][1][1]);
    } else {
        dp[id][0][0] = dp[lch][0][1] + dp[rch][1][0];
        dp[id][0][1] = dp[lch][0][1] + dp[rch][1][1];
        dp[id][1][0] = dp[lch][1][1] + dp[rch][1][0];
        dp[id][1][1] = dp[lch][1][1] + dp[rch][1][1];
    }
    head[id] = head[lch];
    tail[id] = tail[rch];
}

int32_t main() {
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i <= n; i++) d[i] = a[i] - a[i - 1];
    build(1, 1, n);

    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        if (l > 1) upd(1, 1, n, l, x);
        if (r < n) upd(1, 1, n, r + 1, -x);
        cout << dp[1][1][1] << endl;
    }
}

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