Submission #1354256

#TimeUsernameProblemLanguageResultExecution timeMemory
1354256veyis_113Foehn Phenomena (JOI17_foehn_phenomena)C++20
100 / 100
242 ms38632 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll>s(2000001),lz(2000001);
ll v1[2000001];
void lazy(ll l,ll r,ll v){
  if(lz[v]==1e18) return;
  s[v]+=(r-l+1)*lz[v];
  if(l!=r){
    lz[2*v]+=lz[v];
    lz[2*v+1]+=lz[v];
  }
  lz[v]=1e18;
  return;
}
void build(ll l,ll r,ll v){
  if(l==r){
    s[v]=v1[l];
    return;
  }
  ll mid=(l+r)>>1;
  build(l,mid,2*v);
  build(mid+1,r,2*v+1);
  s[v]=s[2*v]+s[2*v+1];
}
void upd(ll l,ll r,ll v,ll ql,ll qr,ll up){
    lazy(l,r,v);
    if(l>qr or r<ql) return;
    if(l>=ql and r<=qr){
        lz[v]=up;
        lazy(l,r,v);
        return ;
    }
    ll mid=(l+r)/2;
    upd(l,mid,2*v,ql,qr,up);
    upd(mid+1,r,2*v+1,ql,qr,up);
    s[v]=s[2*v]+s[2*v+1];
}
ll getans(ll l,ll r,ll v,ll ql,ll qr){
    lazy(l,r,v);
    if(l>qr or r<ql) return 0;
    if(l>=ql and r<=qr){
      lazy(l,r,v);
        return s[v];
    }
    ll mid=(l+r)/2;
    return getans(l,mid,2*v,ql,qr)+getans(mid+1,r,2*v+1,ql,qr);
}
int main(){
  for(ll i=0;i<=200000;i++) lz[i]=1e18;
      ll n,q,s1,t; cin>>n>>q>>s1>>t;
      ll a[n+1];
      for(ll i=0;i<=n;i++){
        cin>>a[i];
      }
      if(n==-1 and q<=2000){
          while(q--){
            ll l,r,x; cin>>l>>r>>x;
            for(ll i=l;i<=r;i++){ 
              a[i]+=x;
            }
            ll ans=0;
            for(ll i=0;i<n;i++){
              if(a[i]<a[i+1]) ans-=(a[i+1]-a[i])*s1;
              else ans+=(a[i]-a[i+1])*t;
            }
            cout<<ans<<endl; 
          } return 0;
      }
      ll sum1=0,sum2=0;
      for(ll i=0;i<n;i++){
        v1[i+1]=a[i]-a[i+1];
        if(a[i]-a[i+1]>0) sum2+=(a[i]-a[i+1]);
        else sum1+=a[i]-a[i+1];
      }
      while(q--){
        ll l,r,x; cin>>l>>r>>x; r++;
        if(v1[l]>=0){
          sum2-=v1[l];
          v1[l]-=x;
          if(v1[l]>=0) sum2+=v1[l];
          else sum1+=v1[l];
        }
        else{
          sum1-=v1[l];
          v1[l]-=x;
          if(v1[l]>=0) sum2+=v1[l];
          else sum1+=v1[l];
        }
        if(r-1==n){ cout<<sum1*s1+sum2*t<<endl; continue;}
        if(v1[r]>=0){
          sum2-=v1[r];
          v1[r]+=x;
          if(v1[r]>=0) sum2+=v1[r];
          else sum1+=v1[r];
        }
        else{
          sum1-=v1[r];
          v1[r]+=x;
          if(v1[r]>=0) sum2+=v1[r];
          else sum1+=v1[r];
        }
        cout<<sum1*s1+sum2*t<<endl;
      }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...