Submission #657830

#	Time	Username	Problem	Language	Result	Execution time	Memory
657830		adaawf	Sjeckanje (COCI21_sjeckanje)	C++17	55 / 110	24 ms	9256 KiB

Main

#include <iostream>
using namespace std;
long long int a[200005], b[200005], t[200005][2][2];
void pull(long long int v, long long int l, long long int r) {
    long long int mid = (l + r) / 2;
    t[v][1][1] = max(t[v * 2][1][0] + t[v * 2 + 1][1][1], max(t[v * 2][1][0] + t[v * 2 + 1][0][1], t[v * 2][1][1] + t[v * 2 + 1][0][1]));
    t[v][0][1] = max(t[v * 2][0][0] + t[v * 2 + 1][1][1], max(t[v * 2][0][0] + t[v * 2 + 1][0][1], t[v * 2][0][1] + t[v * 2 + 1][0][1]));
    t[v][1][0] = max(t[v * 2][1][0] + t[v * 2 + 1][1][0], max(t[v * 2][1][0] + t[v * 2 + 1][0][0], t[v * 2][1][1] + t[v * 2 + 1][0][0]));
    t[v][0][0] = max(t[v * 2][0][0] + t[v * 2 + 1][1][0], max(t[v * 2][0][0] + t[v * 2 + 1][0][0], t[v * 2][0][1] + t[v * 2 + 1][0][0]));
    if ((b[mid] >= 0 && b[mid + 1] >= 0) || (b[mid] <= 0 && b[mid + 1] <= 0)) {
        t[v][1][1] = max(t[v][1][1], t[v * 2][1][1] + t[v * 2 + 1][1][1]);
        t[v][0][1] = max(t[v][0][1], t[v * 2][0][1] + t[v * 2 + 1][1][1]);
        t[v][1][0] = max(t[v][1][0], t[v * 2][1][1] + t[v * 2 + 1][1][0]);
        t[v][0][0] = max(t[v][0][0], t[v * 2][0][1] + t[v * 2 + 1][1][0]);
    }
}
void init(long long int v, long long int l, long long int r) {
    if (l == r) {
        t[v][1][1] = abs(b[l]);
        return;
    }
    long long int mid = (l + r) / 2;
    init(v * 2, l, mid);
    init(v * 2 + 1, mid + 1, r);
    pull(v, l, r);
}
void update(long long int v, long long int l, long long int r, long long int x) {
    if (x < l || x > r) return;
    if (l == r) {
        t[v][1][1] = abs(b[l]);
        return;
    }
    long long int mid = (l + r) / 2;
    update(v * 2, l, mid, x);
    update(v * 2 + 1, mid + 1, r, x);
    pull(v, l, r);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int n, q;
    cin >> n >> q;
    for (long long int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i >= 2) {
            b[i] = a[i] - a[i - 1];
        }
    }
    init(1, 2, n);
    for (long long int jj = 0; jj < q; jj++) {
        long long int x, y, z;
        cin >> x >> y >> z;
        if (x > 1) {
            b[x] += z;
            update(1, 2, n, x);
        }
        if (y < n) {
            b[y + 1] -= z;
            update(1, 2, n, y + 1);
        }
        cout << max(t[1][1][1], max(t[1][0][1], max(t[1][1][0], t[1][0][0]))) << endl;
    }
}

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