제출 #647988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647988		lalala56	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	340 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+9;
ll ST[4*N];
int n,a[N],d[N],q;
ll Me(ll L,ll R,int m,int l){
    ll res;
    if((d[m]>=0||m==l)&&d[m+1]>=0)res=L+R+d[m+1];
    else if((d[m]<=0||m==l)&&d[m+1]<=0)res=L+R-d[m+1];
    else res=L+R;
    return res;
}
void build(int id,int l,int r){
    if(l==r){
        ST[id]=0;
        return;
    }
    int m=(l+r)/2;
    build(id*2,l,m);
    build(id*2+1,m+1,r);
    ST[id]=Me(ST[id*2],ST[id*2+1],m,l);
    //if(l==1&&r==2)cout<<ST[id]<<"L\n";
}
void upd(int id,int l,int r,int v,int x){
    if(v<l||v>r)return;
    if(l==r)return;
    int m=(l+r)/2;
    upd(id*2,l,m,v,x);
    upd(id*2+1,m+1,r,v,x);
    ST[id]=Me(ST[id*2],ST[id*2+1],m,l);
    //if(l==1&&r==2)cout<<ST[id]<<"L\n";
}
void giai(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i]=a[i]-a[i-1];
        //cout<<d[i]<<" ";
    }
    //cout<<'\n';
    d[0]=0;
    build(1,1,n);
    //cout<<ST[1]<<'\n';
    int l,r;
    ll x;
    while(q--){
        cin>>l>>r>>x;
        d[l]+=x;
        d[r+1]-=x;
        //for(int i=1;i<=n;i++)cout<<d[i]<<" ";
        //cout<<'\n';
        upd(1,1,n,l,x);
        if(r<n)upd(1,1,n,r+1,x);
        cout<<ST[1]<<'\n';
    }
}
int main(){
    /*if(fopen("solve.inp","r")){
        freopen("solve.inp","r",stdin);
        freopen("solve.out","w",stdout);
    }*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    giai();
}

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