Submission #1032044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032044		BF001	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	574 ms	47696 KiB

Main

#include<bits/stdc++.h>
using namespace std;
 
#define N 200005
#define int long long

struct node{
    int b[2];
    int dp[2][2];
    node(){
        for (int i = 0; i <= 1; i++){
            for (int j = 0; j <= 1; j++){
                dp[i][j] = b[i] = 0;
            }
        }
    }

    node operator + (node o){
        node rt;
        rt.b[0] = b[0];
        rt.b[1] = o.b[1];
        for (int l = 0; l <= 1; l++){
            for (int r = 0; r <= 1; r++){
                for (int mi1 = 0; mi1 <= 1; mi1++){
                    for (int mi2 = 0; mi2 <= 1; mi2++){
                        if (mi1 && mi2){
                            if (b[1] * o.b[0] > 0){
                                rt.dp[l][r] = max(rt.dp[l][r], dp[l][mi1] + o.dp[mi2][r]);
                            }
                        }
                        else{
                            rt.dp[l][r] = max(rt.dp[l][r], dp[l][mi1] + o.dp[mi2][r]);
                        }
                    }
                }
            }
        }
        return rt;
    }

};

node bit[4 * N];

void ud(int id, int l, int r, int pos, int val){
    if (l > pos || r < pos) return;
    if (l == r){
        bit[id].b[0] += val;
        bit[id].b[1] += val;
        bit[id].dp[1][1] = abs(bit[id].b[0]);
        return;
    }
    int mid = (l + r) >> 1;
    ud(id * 2, l, mid, pos, val);
    ud(id * 2 + 1, mid + 1, r, pos, val);
    bit[id] = bit[id * 2] + bit[id * 2 + 1];
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    int n, m;
    cin >> n >> m;
    int lst = 0;

    for (int i = 1; i <= n; i++){
        int val;
        cin >> val;
        if (i > 1) ud(1, 1, n - 1, i - 1, val - lst);
        lst = val;
    }

    while (m--){
        int l, r, val;
        cin >> l >> r >> val;
        l--;
        if (l >= 1) ud(1, 1, n - 1, l, val);
        if (r <= n - 1) ud(1, 1, n - 1, r, -val);
        int res = 0;
        for (int i = 0; i <= 1; i++){
            for (int j = 0; j <= 1; j++){
                res = max(res, bit[1].dp[i][j]);
            }
        }
        cout << res << "\n";
    }
 
    return 0;
}

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