Submission #932713

#	Time	Username	Problem	Language	Result	Execution time	Memory
932713		ShadowShark	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	333 ms	30336 KiB

Main

#include <bits/stdc++.h>
using namespace std;

   ///***Author: ShadowShark***\\\
Con thuyen nho vuot muon trung nui non

const int maxN = 2e5 + 5;
long long a[maxN];
int n, q;

namespace subtask2 {

long long d[maxN], dp[maxN][2];

void solve() {
    for (int i = 1; i <= q; i++) {
        int l, r, x;
        cin >> l >> r >> x;

        for (int i = l; i <= r; i++)
            a[i] += x;

        for (int i = 1; i < n; i++)
            d[i] = a[i] - a[i + 1];

        d[n] = 0; dp[0][0] = 0; dp[0][1] = 0;

        for (int i = 1; i < n ; i++){
            dp[i][0]= max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1]= max(dp[i - 1][0], dp[i - 1][1] * (d[i] * d[i - 1] >= 0)) + abs(d[i]);
        }

        cout << max(dp[n - 1][0], dp[n - 1][1]) << '\n';
    }
}
}

namespace subtask3 {
    const long long inf = 1e18;
    long long d[maxN];

    struct node {
        long long f[2][2]; /// dp [left chosen?][right chosen?]
    } st[4 * maxN];

    node merge_node(node a, node b, int mid) {
        node temp;

        /// Case d[mid] and d[mid + 1] are diff comp to 0
        temp.f[1][1] = max(a.f[1][1] + b.f[0][1], a.f[1][0] + b.f[1][1]);
        temp.f[1][0] = max(a.f[1][1] + b.f[0][0], a.f[1][0] + b.f[1][0]);
        temp.f[0][1] = max(a.f[0][0] + b.f[1][1], a.f[0][1] + b.f[0][1]);
        temp.f[0][0] = max(a.f[0][1] + b.f[0][0], a.f[0][0] + b.f[1][0]);

        /// Case not
        if ((d[mid] >= 0 && d[mid + 1] >= 0) || (d[mid] < 0 && d[mid + 1] < 0)) {
            temp.f[1][1] = max(a.f[1][1], a.f[1][0]) + max(b.f[1][1], b.f[0][1]);
            temp.f[1][0] = max(a.f[1][1], a.f[1][0]) + max(b.f[1][0], b.f[0][0]);
            temp.f[0][1] = max(a.f[0][1], a.f[0][0]) + max(b.f[0][1], b.f[1][1]);
            temp.f[0][0] = max(a.f[0][1], a.f[0][0]) + max(b.f[0][0], b.f[1][0]);
        }

        return temp;
    }

    void build(int id, int l, int r) {
        if (l == r) {
            st[id].f[1][1] = abs(d[l]);
            return ;
        }

        int mid = (l + r) / 2;

        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);

        st[id] = merge_node(st[2 * id], st[2 * id + 1], mid);
        return ;
    }

    void update(int id, int l, int r, int pos) {
        if (pos < l || r < pos) return ;

        if (l == r) {
            st[id].f[1][1] = abs(d[pos]);
            st[id].f[0][0] = st[id].f[0][1] = st[id].f[1][0] = 0;
            return ;
        }

        int mid = (l + r) / 2;
        update(2 * id, l, mid, pos);
        update(2 * id + 1, mid + 1, r, pos);

        st[id] = merge_node(st[2 * id], st[2 * id + 1], mid);
        return ;
    }

    void solve() {
        for (int i = 1; i < n; i++)
            d[i] = a[i] - a[i + 1];

        build(1, 1, n - 1);

        for (int i = 1; i <= q; i++) {
            int l, r, x;
            cin >> l >> r >> x;

            if (l > 1) {
                d[l - 1] -= x;
                update(1, 1, n - 1, l - 1);
            }

            d[r] += x;
            update(1, 1, n - 1, r);

            cout << max({st[1].f[0][0], st[1].f[0][1], st[1].f[1][0], st[1].f[1][1]}) << '\n';
        }
    }

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

    //freopen("sjeckanje.inp", "r", stdin);
   // freopen("sjeckanje.out", "w", stdout);

    cin >> n >> q;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    /*if (n <= 3000) subtask2::solve();
        else subtask3::solve();*/
    subtask3::solve();

    return 0;
}

Compilation message (stderr)

Main.cpp:4:4: warning: multi-line comment [-Wcomment]
    4 |    ///***Author: ShadowShark***\\\
      |    ^

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