Submission #870942

#	Time	Username	Problem	Language	Result	Execution time	Memory
870942		Ahmed57	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	822 ms	38476 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int borders[2] , dp[2][2];
}seg[800001];
node combine(node a ,node b){
    node res;
    res.borders[0] = a.borders[0];
    res.borders[1] = b.borders[1];
    for(int i = 0;i<2;i++)for(int j = 0;j<2;j++)res.dp[i][j] = 0;
    for(int l = 0;l<2;l++){
        for(int m = 0;m<2;m++){
            for(int o = 0;o<2;o++){
                for(int r = 0;r<2;r++){
                    if(m&o){
                        if((a.borders[1]<0)==(b.borders[0]<0)){
                            res.dp[l][r] = max(res.dp[l][r],a.dp[l][m]+b.dp[o][r]);
                        }
                    }else{
                        res.dp[l][r] = max(res.dp[l][r],a.dp[l][m]+b.dp[o][r]);
                    }
                }
            }
        }
    }
    return res;
}
int arr[200001];
void build(int p,int l,int r){
    if(l==r){
        seg[p].borders[0] = seg[p].borders[1] = arr[l];
        seg[p].dp[0][0] = 0;
        seg[p].dp[0][1] = 0;
        seg[p].dp[1][0] = 0;
        seg[p].dp[1][1] = abs(arr[l]);
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
void update(int p,int l,int r,int idx){
    if(l==r){
        seg[p].borders[0] = seg[p].borders[1] = arr[l];
        seg[p].dp[0][0] = 0;
        seg[p].dp[0][1] = 0;
        seg[p].dp[1][0] = 0;
        seg[p].dp[1][1] = abs(arr[l]);
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx);
    else update(p*2+1,md+1,r,idx);
    seg[p] = combine(seg[p*2],seg[p*2+1]);
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,q;
    cin>>n>>q;
    int vl[n+1];
    for(int i = 1;i<=n;i++)cin>>vl[i];
    for(int i = 1;i<n;i++){
        arr[i] = vl[i+1]-vl[i];
    }
    build(1,1,n-1);
    while(q--){
        int l,r,x;cin>>l>>r>>x;
        if(l>1){
            arr[l-1]+=x;
            update(1,1,n-1,l-1);
        }if(r<n){
            arr[r]-=x;
            update(1,1,n-1,r);
        }
        cout<<max({seg[1].dp[0][0],seg[1].dp[1][0],seg[1].dp[0][1],seg[1].dp[1][1]})<<endl;
    }
}

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