제출 #1209088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209088		lukasuliashvili	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	605 ms	36908 KiB

Main

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fs first 
#define sc second 
const int N=200005; 
int tr[4*N][5],a[N],d[N],d2[N];
pair<int,int> tr2[4*N];
void update(int node,int l,int r, int idx, int x){
    if(l==r){
        tr[node][0]=0;
        tr[node][1]=0;
        tr[node][2]=0;
        tr[node][3]=abs(x);
        if(d2[idx]<0){
            tr2[node].fs=-1;
            tr2[node].sc=-1;
        }
        else{
            tr2[node].fs=1;
            tr2[node].sc=1;
        }
        return;
    }
    int mid=(l+r)/2;
    if(idx <=mid){
        update(2 * node, l, mid, idx, x);       
    }   
    else {
        update(2 * node + 1, mid+1, r, idx, x);   
    }

    if(tr2[2*node].sc*tr2[2*node+1].fs==-1){
        tr[node][1]=max(tr[2*node][3]+tr[2*node+1][0],tr[2*node][1]+tr[2*node+1][1]);
        tr[node][2]=max(tr[2*node][2]+tr[2*node+1][2],tr[2*node][0]+tr[2*node+1][3]);
        tr[node][0]=max(tr[2*node][2]+tr[2*node+1][0],tr[2*node][0]+tr[2*node+1][1]);
        tr[node][3]=max(tr[2*node][3]+tr[2*node+1][2],tr[2*node][1]+tr[2*node+1][3]);
    }
    else{
        tr[node][0]=tr[2*node][2]+tr[2*node+1][1];
        tr[node][1]=tr[2*node][3]+tr[2*node+1][1];
        tr[node][2]=tr[2*node][2]+tr[2*node+1][3];
        tr[node][3]=tr[2*node][3]+tr[2*node+1][3];
    }   
    tr2[node].fs=tr2[2*node].fs;
    tr2[node].sc=tr2[2*node+1].sc;
    
}
signed main() {
    int n, t;
    cin>>n>>t;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    for(int i=2; i<=n; i++){
        int idx=i-1;
        d[idx]=abs(a[i]-a[i-1]);
        d2[idx]=a[i]-a[i-1];
    }
    for(int i=1; i<n; i++){
        update(1,1,n-1,i,d[i]);
    }
    while(t--){
        int l,r,x;cin>>l>>r>>x;
        if(l!=1){
            d2[l-1]+=x;
            update(1,1,n-1,l-1,d2[l-1]);
            
        }
        if(r!=n){
            d2[r]-=x;
            update(1,1,n-1,r,d2[r]);
            
        }
        
        cout<<tr[1][3]<<endl;
    }
}   

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