Submission #230173

#	Time	Username	Problem	Language	Result	Execution time	Memory
230173		Haunted_Cpp	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	209 ms	16376 KiB

foehn_phenomena

#include <iostream>
#include <vector>

typedef long long i64;

using namespace std;

const int N = 2e5 + 5;

i64 a [N], temp [N];

struct FenwickTree {
  vector<i64> bit;
  const int L;
  FenwickTree (int n) : L (n + 5) {
    bit.clear();
    bit.resize(L);
  }
  void update (int idx, i64 delta) {  
    for (; idx < L; idx += idx & (- idx)) {
      bit[idx] += delta;
    }
  }
  void range_update (int lo, int hi, i64 delta) {
    update (lo, + delta);
    update (hi + 1, - delta);
  }
  i64 query (int idx) {
    i64 res = 0;
    for (; idx > 0; idx -= idx & (- idx)) {
      res += bit[idx];
    }
    return res;
  }
};

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q, temp_aumentar, temp_diminuir;
  cin >> n >> q >> temp_aumentar >> temp_diminuir;
  ++n;
  for (int i = 0; i < n; i++) cin >> a[i];
  temp[0] = 0;
  for (int i = 1; i < n; i++) {
    int d = a[i] - a[i - 1];
    if (d >= 0) {
      temp[i] = temp[i - 1] - 1LL * temp_aumentar * d;
    } else {
      temp[i] = temp[i - 1] - 1LL * temp_diminuir * d;
    }
  }
  FenwickTree valores (n), somas (n);
  for (int i = 1; i < n; i++) {
    valores.range_update (i, i, a[i]);
    somas.range_update (i, i, temp[i]);
  }
  while (q--) {
    int l, r, delta;
    cin >> l >> r >> delta;
    i64 diff_inicial = somas.query (l);
    i64 diff_final = somas.query (r + 1);
    valores.range_update(l, r, delta);
    // Atualizar [L - R]
    long long diff = -1;
    i64 d = valores.query (l) - valores.query (l - 1);
    if (d >= 0) {
      diff = somas.query(l - 1) - 1LL * temp_aumentar * d;
      diff -= diff_inicial;
    } else {
      diff = somas.query(l - 1) - 1LL * temp_diminuir * d;
      diff -= diff_inicial;
    }
    somas.range_update (l, r, diff);  
    // Atualizar [R + 1, MAX]  
    diff = -1;
    d = valores.query (r + 1) - valores.query (r);
    if (d >= 0) {
      diff = somas.query(r) - 1LL * temp_aumentar * d;
      diff -= diff_final;
    } else {
      diff = somas.query(r) - 1LL * temp_diminuir * d;
      diff -= diff_final;
    }
    somas.range_update (r + 1, n + 1, diff); 
    cout << somas.query (n - 1) << '\n';
  }
  return 0;
}

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