Submission #1148778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148778		buzdi	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	576 ms	42592 KiB

Main

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int NMAX = 2e5;

struct TreeNode {
    ll value_at_end[2] = {};
    // 0 --> The value of the left end
    // 1 --> The value of the right end

    ll dp[2][2] = {};
    // dp[i][j] = The maximum sum on this interval
    //            with the left end not taken / taken
    //            and the right end not taken / taken

    TreeNode() {}
    TreeNode(int value) {
        value_at_end[0] = value_at_end[1] = value;
        dp[1][1] = abs(value); // We need the absolute value for the dp to represent the value of the segment
    }
};

struct AINT {
    TreeNode aint[4 * NMAX + 1];

    TreeNode UpdateNode(TreeNode left, TreeNode right) {
        TreeNode answer;
        answer.value_at_end[0] = left.value_at_end[0]; // The value of the left end will be the one from the left interval
        answer.value_at_end[1] = right.value_at_end[1]; // The value of the right end will be the one from the right interval

        for(int i = 0; i < 2; i++) {
            for(int k = 0; k < 2; k++) {
                for(int p = 0; p < 2; p++) {
                    for(int j = 0; j < 2; j++) {
                        if(k && p) {
                            // It's optimal to maintain the interval monotonic
                            // Thus, the value at the right end of the left interval and the value at the left end of the right interval should have the same sign
                            if((left.value_at_end[1] < 0) == (right.value_at_end[0] < 0)) {
                                answer.dp[i][j] = max(answer.dp[i][j], left.dp[i][k] + right.dp[p][j]);
                            }
                        }
                        else {
                            // One of the ends is not taken into consideration
                            // --> We cut the segment right here
                            answer.dp[i][j] = max(answer.dp[i][j], left.dp[i][k] + right.dp[p][j]);
                        }
                    }
                }
            }
        }
        return answer;
    }

    void Build(int node, int left, int right, int* d) {
        if(left == right) {
            aint[node] = TreeNode(d[left]);
            return;
        }

        int mid = (left + right) / 2;
        Build(node * 2, left, mid, d);
        Build(node * 2 + 1, mid + 1, right, d);
        aint[node] = UpdateNode(aint[node * 2], aint[node * 2 + 1]);
    }

    void Update(int node, int left, int right, int pos, int value) {
        if(left == right) {
            // We just increase the values and assign to the dp the new absolute value
            aint[node].value_at_end[0] += value;
            aint[node].value_at_end[1] += value;
            aint[node].dp[1][1] = abs(aint[node].value_at_end[0]);
            return;
        }

        int mid = (left + right) / 2;
        if(pos <= mid) {
            Update(node * 2, left, mid, pos, value);
        }
        else {
            Update(node * 2 + 1, mid + 1, right, pos, value);
        }
        aint[node] = UpdateNode(aint[node * 2], aint[node * 2 + 1]);
    }
}aint;

int n, q;
int a[NMAX + 1];
int d[NMAX + 1];

signed 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];
    }

    // The difference array
    // The absolute value of the sum of those values for a monotonic subarray represents the value of the segment
    for(int i = 1; i <= n - 1; i++) {
        d[i] = a[i + 1] - a[i];
    }

    aint.Build(1, 1, n - 1, d);
    while(q--) {
        int left, right, value;
        cin >> left >> right >> value;

        // The values between [left + 1, right - 1] don't matter
        // They get canceled in the summation in the 'd' array WHATEVER VALUES THEY HAVE
        if(left - 1 >= 1) {
            aint.Update(1, 1, n - 1, left - 1, value); // d[left - 1] = a[left] - a[left - 1] --> We should add
        }
        if(right <= n - 1) {
            aint.Update(1, 1, n - 1, right, -value); // d[right] = a[right + 1] - a[right] --> We should substract
        }
        cout << aint.aint[1].dp[1][1] << '\n'; // We need both ends for the query
    }

    return 0;
}

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