Submission #1285398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285398		dobri_oke	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	369 ms	31048 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define int long long

const int N = 1e6+100;
int n, q, a[N], d[N], dp[N * 4][2][2], L[N * 4], R[N * 4];

void merge(int v, int v2, int v3){
    L[v] = L[v2];
    R[v] = R[v3];
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++) dp[v][i][j] = 0;
    }
    for(int lft = 0; lft < 2; lft++){
        for(int m = 0; m < 2; m++){
            for(int o = 0; o < 2; o++){
                for(int rgt = 0; rgt < 2; rgt++){
                    if((m && o) && (R[v2]==0 || L[v3]==0)) continue;
                    if((m && o) && (R[v2]<0) != (L[v3]<0)) continue;
                    dp[v][lft][rgt] = max(dp[v][lft][rgt], dp[v2][lft][m] + dp[v3][o][rgt]);
                }
            }
        }
    }
}

void build(int v, int l, int r){
    if(l == r){
        dp[v][0][0] = dp[v][0][1] = dp[v][1][0] = 0;
        L[v] = R[v] = d[l];
        dp[v][1][1] = (d[l]!=0 ? abs(d[l]) : 0);
        return;
    }
    int m = (l + r) / 2;
    build(v + v, l, m);
    build(v + v + 1, m + 1, r);
    merge(v, v + v, v + v + 1);
}

void upd(int v, int l, int r, int pos, int x){
    if(l == r){
        L[v] += x;
        R[v] += x;
        dp[v][1][1] = (L[v]!=0 ? abs(L[v]) : 0);
        dp[v][0][0] = dp[v][0][1] = dp[v][1][0] = 0;
        return;
    }
    int m = (l + r) / 2;
    if(pos <= m) upd(v + v, l, m, pos, x);
    else upd(v + v + 1, m + 1, r, pos, x);
    merge(v, v + v, v + v + 1);
}
void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < n; i++) d[i] = a[i + 1] - a[i];
    build(1, 1, n - 1);
    while(q--){
        int l, r, x;
        cin >> l >> r >> x;
        if(l-1 >= 1) upd(1, 1, n-1, l-1, x);
        if(r < n) upd(1, 1, n-1, r, -x);
        cout << dp[1][1][1] << '\n';
    }
}

signed main(){   
    ios_base::sync_with_stdio(0);   cin.tie(0);
    //freopen("promote.in","r",stdin);
    //freopen("promote.out","w",stdout);
    int tt=1;
   // cin >> tt;
    while(tt--){
        solve();
    }
}

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