Submission #1087565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087565		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	372 ms	27984 KiB

Main

#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_) for(int V_=(A_), V_##_END=(B_); V_>=V_##_END; V_--)
#ifdef _WIN32
#define long __int64
#endif
using namespace std;
const int MAXN=2e5+10; const long INFL=1e18;
int n,qn; long A[MAXN];
void tomax(long& x,long y){ x=max(x,y); }
struct SGT{
#define ls (u*2)
#define rs (u*2+1)
#define mid ((l+r)/2)
    struct{ long mx[2][2]; } T[MAXN*4];
    void pushup(int u,int l,int r){
        RNG(tl,0,1){
            RNG(tr,0,1){
                T[u].mx[tl][tr]=0;
                tomax(T[u].mx[tl][tr],T[ls].mx[tl][0]+T[rs].mx[0][tr]);
                tomax(T[u].mx[tl][tr],T[ls].mx[tl][0]+T[rs].mx[1][tr]);
                tomax(T[u].mx[tl][tr],T[ls].mx[tl][1]+T[rs].mx[0][tr]);
                if((A[mid]>=0&&A[mid+1]>=0)||(A[mid]<=0&&A[mid+1]<=0)) tomax(T[u].mx[tl][tr],T[ls].mx[tl][1]+T[rs].mx[1][tr]);
            }
        }
    }
    void build(int u,int l,int r){
        if(l==r){
            T[u].mx[0][0]=0,T[u].mx[1][1]=labs(A[l]);
            T[u].mx[0][1]=T[u].mx[1][0]=0;
            return;
        }
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(u,l,r);
    }
    void upd(int u,int l,int r,int i){
        if(l==r){
            T[u].mx[0][0]=0,T[u].mx[1][1]=labs(A[i]);
            T[u].mx[0][1]=T[u].mx[1][0]=0;
            return;
        }
        if(i<=mid) upd(ls,l,mid,i);
        else upd(rs,mid+1,r,i);
        pushup(u,l,r);
    }
#undef ls
#undef rs
#undef mid
} sgt;
int main(){
#if defined(_LOCAL_)
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#else
#endif
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>qn;
    RNG(i,1,n) cin>>A[i];
    IRNG(i,n,1) A[i]-=A[i-1];
    sgt.build(1,2,n);
    RNG(_,1,qn){
        int l,r; long x; cin>>l>>r>>x;
        A[l]+=x,A[r+1]-=x;
        if(l>=2) sgt.upd(1,2,n,l);
        if(r+1<=n) sgt.upd(1,2,n,r+1);
        auto ans=max({sgt.T[1].mx[0][0],sgt.T[1].mx[0][1],sgt.T[1].mx[1][0],sgt.T[1].mx[1][1]});
        cout<<ans<<"\n";
    }
}

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