Submission #1354293

#TimeUsernameProblemLanguageResultExecution timeMemory
1354293vjudge1Foehn Phenomena (JOI17_foehn_phenomena)C++20
10 / 100
375 ms38488 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;
      }
      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; 
              upd(1,n,1,l,l,x);
              upd(1,n,1,r+1,r+1,-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...