Submission #657823

#	Time	Username	Problem	Language	Result	Execution time	Memory
657823		HungAnhGoldIBO2020	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	459 ms	28016 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+2;
int ar[N],it[4*N][2][2];
bool samesign(int a,int b){
    if(a==0||b==0){
        return true;
    }
    if(a>0&&b>0){
        return true;
    }
    if(a<0&&b<0){
        return true;
    }
    return false;
}
void pull(int idx,int l,int r){
    int mid=(l+r)>>1;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            it[idx][i][j]=max(it[2*idx][i][0]+it[2*idx+1][1][j],max(it[2*idx][i][0]+it[2*idx+1][0][j],it[2*idx][i][1]+it[2*idx+1][0][j]));
            if(samesign(ar[mid],ar[mid+1])){
                it[idx][i][j]=max(it[idx][i][j],it[2*idx][i][1]+it[2*idx+1][1][j]);
            }
        }
    }
}
void init(int idx,int l,int r){
    if(l==r){
        if(ar[l]<0){
            it[idx][1][1]=-ar[l];
        }
        else{
            it[idx][1][1]=ar[l];
        }
        return;
    }
    int mid=(l+r)>>1;
    init(2*idx,l,mid);
    init(2*idx+1,mid+1,r);
    pull(idx,l,r);
}
void upd(int idx,int l,int r,int pos){
    if(pos>r||pos<l){
        return;
    }
    if(l==r){
        if(ar[l]<0){
            it[idx][1][1]=-ar[l];
        }
        else{
            it[idx][1][1]=ar[l];
        }
        return;
    }
    int mid=(l+r)>>1;
    upd(2*idx,l,mid,pos);
    upd(2*idx+1 ,mid+1,r,pos);
    pull(idx,l,r);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q,i,j,k,l;
    cin>>n>>q;
    if(n==1){
        for(i=1;i<=q;i++){
            cout<<0<<'\n';
        }
        return 0;
    }
    for(i=1;i<=n;i++){
        cin>>j;
        if(i>1){
            ar[i-1]=j-k;
        }
        k=j;
    }
    n--;
    init(1,1,n);
    for(i=1;i<=q;i++){
        //cout<<i<<" KEK"<<endl;
        cin>>j>>k>>l;
        if(j>1){
            ar[j-1]+=l;
            upd(1,1,n,j-1);
        }
        if(k<=n){
            ar[k]-=l;
            upd(1,1,n,k);
        }
        /*
        for(j=1;j<=n;j++){
            cout<<ar[j]<<' ';
        }
        cout<<'\n';
        */
        cout<<max(max(it[1][0][0],it[1][1][1]),max(it[1][0][1],it[1][1][0]))<<'\n';
    }
}
/*
4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
*/

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