제출 #993543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993543		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	351 ms	38560 KiB

Main

/*
    Author: tminh_hk20
    Task:
*/

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define getbit(x,y) ((x) & (1ll<<(y)));
#define turnon(x,y) ((x) | (1ll<<(y)));
#define turnoff(x,y) ((x) ^ (1ll<<(y)));

using namespace std;
const int N =2e5;
const int MOD = 998244353;

ll n, q, a[N+10], b[N+10];

struct node{
    ll f[2][2], lef, rig;
}st[4*N+10];

node combine(node a, node b){
    node res;
    res.lef = a.lef;
    res.rig = b.rig;

    res.f[0][0] = max({0ll,a.f[0][0]+b.f[1][0],a.f[0][1]+b.f[0][0], a.f[0][0]+b.f[0][0]});
    res.f[1][0] = max({0ll,a.f[1][0]+b.f[1][0], a.f[1][1]+b.f[0][0], a.f[1][0]+b.f[0][0]});
    res.f[0][1] = max({0ll,a.f[0][1]+b.f[0][1], a.f[0][0]+b.f[1][1],a.f[0][0]+b.f[0][1]});
    res.f[1][1] = max({0ll,a.f[1][0]+b.f[1][1], a.f[1][1]+b.f[0][1],a.f[1][0]+b.f[0][1]});
    if (a.rig*b.lef>=0){
        res.f[0][0] = max(res.f[0][0], a.f[0][1]+b.f[1][0]);
        res.f[1][0] = max(res.f[1][0], a.f[1][1]+b.f[1][0]);
        res.f[0][1] = max(res.f[0][1], a.f[0][1]+b.f[1][1]);
        res.f[1][1] = max(res.f[1][1], a.f[1][1]+b.f[1][1]);
    }

    return res;
}

void build(int id,int l, int r){
    if (l==r){
        st[id].f[1][1] = abs(b[l]);
        st[id].f[0][0] = 0;
        st[id].f[1][0] = 0;
        st[id].f[0][1] = 0;
        st[id].lef = st[id].rig = b[l];
        return;
    }

    int m = (l+r)/2;
    build(2*id,l,m);
    build(2*id+1,m+1,r);
    st[id] = combine(st[2*id],st[2*id+1]);
//    cout <<">"<<id<<" "<<l<<" "<<r<<" "<<" "<<st[id].lef<<" "<<st[id].rig<<" <> "<<st[id].f[1][0]<<" "<<st[id].f[0][1]<<" "<<st[id].f[0][0]<<" "<<st[id].f[1][1]<<endl;
}

void up(int id, int l, int r, int i, int val){
    if (i> r || i<l) return;
    if (l==r && i==l){
        st[id].f[1][1] = abs(val);
        st[id].f[0][0] = 0;
        st[id].f[1][0] = 0;
        st[id].f[0][1] = 0;
        st[id].lef = st[id].rig = val;
        return;
    }

    int m = (l+r)/2;
    up(2*id,l,m,i,val);
    up(2*id+1,m+1,r,i,val);
    st[id] = combine(st[2*id],st[2*id+1]);
}

void solve(){
    cin>> n>> q;
    for (int i=1;i<=n;i++) cin>> a[i];

    for (int i=1;i<n;i++) b[i] = a[i+1]- a[i];
    n--;
    build(1,1,n);
    while(q--){
        int l, r, x; cin>>l>>r>>x;
        b[l-1] +=x; b[r]-=x;
        up(1,1,n,l-1,b[l-1]);
        up(1,1,n,r,b[r]);

        node res = st[1];
        cout << max({res.f[0][0],res.f[1][0],res.f[0][1],res.f[1][1]})<<endl;
//        for (int i=1;i<=n;i++) cout << b[i]<<" "; cout<<endl;
    }



}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

//    freopen("bai.inp","r",stdin);
//    freopen("bai.out","w",stdout);

    int T = 1;
    while(T--) solve();
}

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