Submission #1118238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118238		Thunnus	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	729 ms	50760 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

struct SegTree{
    struct Node{
        int dp[2][2] = {};
        int borders[2] = {};
        Node() {}
        Node(int val) {
			dp[0][0] = dp[0][1] = dp[1][0] = 0;
            dp[1][1] = abs(val);
            borders[0] = borders[1] = val;
        }

        inline void node_update(int val){
            borders[0] += val, borders[1] += val;
            dp[1][1] = abs(borders[0]);
            return;
        }
    };
    vector<Node> st;
    SegTree(int n) : st(4 * n) {}

    inline Node combine(Node &a, Node &b){
        Node c;
        c.borders[0] = a.borders[0], c.borders[1] = b.borders[1];
        // [	 ][	 ]
		// l	 mo	 r
		// m and o same -> taken segments are combined
        for(int l = 0; l < 2; l++){
            for(int r = 0; r < 2; r++){
                for(int m = 0; m < 2; m++){
                    for(int o = 0; o < 2; o++){
                        if(m && o){
                            if((a.borders[1] < 0) == (b.borders[0] < 0)){
                                c.dp[l][r] = max(c.dp[l][r], a.dp[l][m] + b.dp[o][r]);
                            }
                        }
                        else{
                            c.dp[l][r] = max(c.dp[l][r], a.dp[l][m] + b.dp[o][r]);
                        }
                    }
                }
            }
        }
        return c;
    }

    inline void update(int pos, int val, int v, int tl, int tr){
        if(tl == tr){
            st[v].node_update(val);
            return;
        }
        int mid = (tl + tr) / 2;
        if(pos <= mid){
            update(pos, val, 2 * v, tl, mid);
        }
        else{
            update(pos, val, 2 * v + 1, mid + 1, tr);
        }
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        return;
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q;
    cin >> n >> q;
    vi a(n), diff(n - 1);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(i){
            diff[i - 1] = a[i] - a[i - 1];
        }
    }

    SegTree st(n - 1);
    for(int i = 0; i < n - 1; i++){
        st.update(i + 1, diff[i], 1, 1, n - 1);
    }
    while(q--){
        int l, r, x;
        cin >> l >> r >> x;
        if(l - 1 >= 1) st.update(l - 1, x, 1, 1, n - 1);
        if(r <= n - 1) st.update(r, -x, 1, 1, n - 1);
        cout << st.st[1].dp[1][1] << "\n";
    }
    return 0;
}

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