Submission #923865

#	Time	Username	Problem	Language	Result	Execution time	Memory
923865		Aiperiii	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	434 ms	21976 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e5+5;
int a[N],ans[N*4],t[N*4];
int n,q,s,T;
void build(int v,int tl,int tr){
   if(tl==tr){
      if(tl+1<=n){
         if(a[tl+1]>a[tl])ans[v]=(a[tl]-a[tl+1])*s;
         else ans[v]=(a[tl]-a[tl+1])*T;
      }
   }
   else{
      int tm=(tl+tr)/2;
      build(v*2,tl,tm);
      build(v*2+1,tm+1,tr);
      ans[v]=ans[v*2]+ans[v*2+1];
   }
}
void update(int v,int tl,int tr,int pos,int x){
   if(tl==tr){
      ans[v]=x;
   }
   else{
      int tm=(tl+tr)/2;
      if(pos<=tm)update(v*2,tl,tm,pos,x);
      else update(v*2+1,tm+1,tr,pos,x);
      ans[v]=ans[v*2]+ans[v*2+1];
   }
}


void add(int v,int tl,int tr,int l,int r,int x){
   if(r<tl or l>tr)return;
   if(l<=tl && tr<=r){
      t[v]+=x;
      return;
   }
   int tm=(tl+tr)/2;
   add(v*2,tl,tm,l,r,x);
   add(v*2+1,tm+1,tr,l,r,x);
}
int get(int v,int tl,int tr,int pos){
   if(tl==tr)return t[v];
   else{
      int tm=(tl+tr)/2;
      if(pos<=tm)return t[v]+get(v*2,tl,tm,pos);
      else return t[v]+get(v*2+1,tm+1,tr,pos);
   }
}
signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   cin>>n>>q>>s>>T;
   n++;
   for(int i=1;i<=n;i++){
      cin>>a[i];
   }
   build(1,1,n);
   while(q--){
      int l,r,x;
      cin>>l>>r>>x;
      l++;r++;
      add(1,1,n,l,r,x);
      if(l-1>=1){
         int a1=a[l-1]+get(1,1,n,l-1);
         int a2=a[l]+get(1,1,n,l);
         int new_val=0;
         
         if(a1<a2)new_val=(a1-a2)*s;
         else new_val=(a1-a2)*T;
         
         update(1,1,n,l-1,new_val);
      }
      if(r+1<=n){
         int a1=a[r]+get(1,1,n,r);
         int a2=a[r+1]+get(1,1,n,r+1);
         int new_val=0;
         if(a1<a2)new_val=(a1-a2)*s;
         else new_val=(a1-a2)*T;
         update(1,1,n,r,new_val);
      }
      cout<<ans[1]<<"\n";
   }
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60