Submission #855820

#	Time	Username	Problem	Language	Result	Execution time	Memory
855820		lambd47	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	10 / 100	529 ms	17160 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2e5+7;
struct node{
  int soma,altura;
};
int sobe,desce;
node seg[4*MAXN];
int arr[MAXN];

node merge(node a, node b){
  int retorna=0;
  retorna+=a.soma+b.soma;
  retorna-=(a.altura*(a.altura>0)*sobe+a.altura*(a.altura<0)*desce);
  retorna-=(b.altura*(b.altura>0)*sobe+b.altura*(b.altura<0)*desce);
  return{retorna,0};
}


void build(int pos, int ini, int fim){
  if(ini==fim){
    seg[pos]={0,arr[ini]-arr[ini-1]};
    return;
  }
  int m=(ini+fim)/2;
  int e=2*pos,d=2*pos+1;
  build(e,ini,m);
  build(d,m+1,fim);
  seg[pos]=merge(seg[e],seg[d]);
}

void query(int pos, int ini, int fim,int val, int ind,int direita){
  if(ini>ind || fim<ind){
    return;
  }
  if(ini==fim){
    seg[pos].altura+=val*direita;
    return;
  }
  int m=(ini+fim)/2;
  int e=2*pos,d=2*pos+1;
  query(e,ini,m,val,ind,direita);
  query(d,m+1,fim,val,ind,direita);
  seg[pos]=merge(seg[e],seg[d]);
}


int32_t main(){
  int n,q;
  cin>>n>>q>>sobe>>desce;
  for(int i=0;i<=n;i++){
    cin>>arr[i];
  }
  build(1,1,n);
  while(q--){
    int a,b,val;
    cin>>a>>b>>val;
    if(a!=0)query(1,1,n,val,a,1);
    if(b!=n)query(1,1,n,val,b+1,-1);
    cout<<seg[1].soma<<"\n";
  }

}

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