Submission #1283387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283387		lechaa	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	404 ms	9768 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define int long long

int t[4*200002];

void update(int i, int l, int r, int i1, int v){
  if(l == r){
    t[i] += v;
    return;
  }
  int mid = (l + r)/2;
  if(i1 <= mid){
    update(i*2, l, mid, i1, v);
  }else{
    update(i*2+1, mid+1, r, i1, v);
  }
  t[i] = t[i*2] + t[i*2+1];
}

int query(int i, int l, int r, int l1, int r1){
  if(l > r1 || l1 > r) return 0;
  if(l1 <= l && r1 >= r){
    return t[i];
  }
  int mid = (l+r)/2;
  return (query(i*2, l, mid, l1, r1) + query(i*2+1, mid+1, r, l1, r1));
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q, s, tr; cin >> n >> q >> s >> tr;
  vector<int> x(n+1);
  for(int i = 0; i <= n; i++){
    cin >> x[i];
  }
  int co = 0;
  for(int i = 1; i <= n; i++){
    if(x[i-1] < x[i]){
      co -= s * abs(x[i-1] - x[i]);
    }else{
      co += tr * abs(x[i-1] - x[i]);
    }
  }
  while(q--){
    int l, r, c; cin >>  l >> r >> c;
    //l, l-1
    if(l != 0){
      int a, b;
      a = x[l-1] + query(1, 0, n+1, 0, l-1);
      b = x[l] + query(1, 0, n+1, 0, l);
      if(a < b){
        co += s * abs(a-b);
      }else{
        co -= tr * abs(a-b);
      }
    }
    //r, r+1
    if(r != n){
      int a, b;
      a = x[r] + query(1, 0, n+1, 0, r);
      b = x[r+1] + query(1, 0, n+1, 0, r+1);
      if(a < b){
        co += s * abs(a-b);
      }else{
        co -= tr * abs(a-b);
      }
    }
    update(1, 0, n+1, l, c);
    update(1, 0, n+1, r+1, -c);
    //l, l-1
    if(l != 0){
      int a, b;
      a = x[l-1] + query(1, 0, n+1, 0, l-1);
      b = x[l] + query(1, 0, n+1, 0, l);
      if(a < b){
        co -= s * abs(a-b);
      }else{
        co += tr * abs(a-b);
      }
    }
    //r, r+1
    if(r != n){
      int a, b;
      a = x[r] + query(1, 0, n+1, 0, r);
      b = x[r+1] + query(1, 0, n+1, 0, r+1);
      if(a < b){
        co -= s * abs(a-b);
      }else{
        co += tr * abs(a-b);
      }
    }
    cout << co << "\n";
  }
  return 0;
}

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