Submission #1176562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176562		giorgi123glm	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	371 ms	23892 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;

#define int long long

int siz = 1, N = 0, m = 0, Q = 0;
vector <int> v;
vector <int> diff;
vector <array <array <int, 2>, 2> > segtree;

void segtree_update (int ind, int u, int l, int r) {
    if (r < ind || ind < l)
        return;

    if (l == ind && r == ind) {
        // update start
        segtree[u][0][0] = 0;
        segtree[u][0][1] = -2e4;
        segtree[u][1][0] = -2e4;
        segtree[u][1][1] = abs (diff[l]);
        return;
    }

    const int mid = (l + r) / 2;
    segtree_update (ind, 2 * u, l, mid);
    segtree_update (ind, 2 * u + 1, mid + 1, r);

    // time for merging
    for (int lb : {0, 1})
        for (int rb : {0, 1}) {
            segtree[u][lb][rb] = segtree[2 * u][lb][0] + segtree[2 * u + 1][0][rb];
            segtree[u][lb][rb] = max (segtree[u][lb][rb], segtree[2 * u][lb][1] + segtree[2 * u + 1][0][rb]);
            segtree[u][lb][rb] = max (segtree[u][lb][rb], segtree[2 * u][lb][0] + segtree[2 * u + 1][1][rb]);
            if (diff[mid] * diff[mid + 1] >= 0)
                segtree[u][lb][rb] = max (segtree[u][lb][rb], segtree[2 * u][lb][1] + segtree[2 * u + 1][1][rb]);
        }
}

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

    cin >> N >> Q;

    m = N - 1;
    while (siz < m)
        siz *= 2;
    segtree.resize (2 * siz);

    v.resize (siz + 2);
    diff.resize (siz + 1);
    for (int i = 1; i <= N; i++)
        cin >> v[i];

    for (int i = 1; i <= m; i++)
        diff[i] = v[i + 1] - v[i];
    for (int i = m + 1; i <= siz; i++)
        diff[i] = 0;

    for (int i = 1; i <= siz; i++)
        segtree_update (i, 1, 1, siz);

    // for (int i = 1; i < 2 * siz; i++) {
    //     if (__builtin_popcount (i) == 1)
    //         cout << '\n';
    //     cout << segtree[i][0][0] << ' ' << segtree[i][1][0] << ' ' << segtree[i][0][1] << ' ' << segtree[i][1][1] << " | ";
    // }

    while (Q--) {
        int L = 0, R = 0, X = 0;
        cin >> L >> R >> X;
        if (L - 1 >= 1) {
            diff[L - 1] += X;
            segtree_update (L - 1, 1, 1, siz);
        }

        if (R <= m) {
            diff[R] -= X;
            segtree_update (R, 1, 1, siz);
        }

        // for (int i = 1; i <= siz; i++)
        //     cout << diff[i] << ' ';
        // cout << '\n';
        // for (int i = 1; i < 2 * siz; i++) {
        //     if (__builtin_popcount (i) == 1)
        //         cout << '\n';
        //     cout << segtree[i][0][0] << ' ' << segtree[i][1][0] << ' ' << segtree[i][0][1] << ' ' << segtree[i][1][1] << " | ";
        // }
        // cout << "\n\n";

        int ans = -2e9;
        for (int lb : {0, 1})
            for (int rb : {0, 1})
                ans = max (ans, segtree[1][lb][rb]);
        cout << ans << '\n';
    }
}

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