Submission #1353841

#TimeUsernameProblemLanguageResultExecution timeMemory
1353841vjudge1Foehn Phenomena (JOI17_foehn_phenomena)C++20
0 / 100
341 ms38832 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]==0) return;
  s[v]+=(r-l+1)*lz[v];
  if(l!=r){
    lz[2*v]+=lz[v];
    lz[2*v+1]+=lz[v];
  }
  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)>>1;
  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){
        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(){
      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;
      }
      if(s1==t){
            for(ll i=0;i<=n;i++){
              v1[i+1]=a[i+1]-a[i];
            }
            build(1,n,1);
            while(q--){
              ll l,r,x; cin>>l>>r>>x; l--; r--;
              upd(1,n,1,l,r,x);
              cout<<getans(1,n,1,1,n)*s1<<endl;
            }
      }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...