Submission #1273286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273286		anbg	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	1 ms	332 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N=2e5+3;
int a[N];
int d[N];

struct da{
    int best, bo2, bodau, bocuoi, lef, rig;
} t[4*N];

da mergee(da L, da R) {
    da res;
    res.lef = L.lef;
    res.rig = R.rig;
    res.best = max(L.best + R.bodau, R.best + L.bocuoi);
    res.bodau = max(L.bodau + R.bodau, L.bo2 + R.best);
    res.bocuoi = max(R.bocuoi + L.bocuoi, R.bo2 + L.best);
    res.bo2 = max(L.bo2 + R.bocuoi, R.bo2 + L.bodau);

    if (d[L.rig] * d[R.lef] >= 0) {
        res.best = max(L.best, L.bocuoi) + max(R.best, R.bodau);
        res.bodau = max(L.bodau, L.bo2) + max(R.best, R.bodau);
        res.bocuoi = max(L.bocuoi, L.best) + max(R.bocuoi, R.bo2);
        res.bo2 = max(L.bodau, L.bo2) + max(R.bocuoi, R.bo2);
    }
    return res;
}

void update(int id, int l, int r, int p, int val) {
    if (l > p || r < p) return;
    if (l == r) {
        t[id] = {abs(val), 0, 0, 0, l, r};
        return;
    }
    int mid = (l + r) >> 1;
    update(2 * id, l, mid, p, val);
    update(2 * id + 1, mid + 1, r, p, val);
    t[id] = mergee(t[2 * id], t[2 * id + 1]);
}

da get(int id, int l, int r, int L, int R) {
    if (l > R || r < L) return {0, 0, 0, 0, 0, 0};
    if (L <= l && r <= R) return t[id];
    int mid = (l + r) >> 1;
    return mergee(get(2 * id, l, mid, L, R), get(2 * id + 1, mid + 1, r, L, R));
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        d[i] = a[i] - a[i + 1];
    }
    for (int i = 1; i < n; i++) {
        update(1, 1, n - 1, i, d[i]);
    }
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        update(1, 1, n - 1, l - 1, d[l - 1] - x);
        d[l - 1] -= x;
        update(1, 1, n - 1, r, d[r] + x);
        d[r] += x;
        cout << t[1].best << '\n';
    }
    return 0;
}

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