Submission #520700

#TimeUsernameProblemLanguageResultExecution timeMemory
520700Alex_tz307Foehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
134 ms11560 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int kN = 2e5;
int n, q, s, t, aib[1 + kN];

int tempChange(int x, int y) {
  if (x < y) {
    return s * (x - y);
  }
  return t * (x - y);
}

void update(int x, int v) {
  for (int i = x; i <= n; i += i & -i) {
    aib[i] += v;
  }
}

void update(int l, int r, int v) {
  update(l, v);
  update(r + 1, -v);
}

int query(int x) {
  int ans = 0;
  for (int i = x; i > 0; i = i & (i - 1)) {
    ans += aib[i];
  }
  return ans;
}

void modify(int &temp, int l, int r, int sgn) {
  temp += sgn * tempChange(query(l - 1), query(l));
  if (r + 1 <= n) {
    temp += sgn * tempChange(query(r), query(r + 1));
  }
}

void testCase() {
  cin >> n >> q >> s >> t;
  int temp = 0, last = 0;
  for (int i = 0; i <= n; ++i) {
    int x;
    cin >> x;
    if (i) {
      temp += tempChange(last, x);
      update(i, i, x);
    }
    last = x;
  }
  for (int i = 0; i < q; ++i) {
    int l, r, k;
    cin >> l >> r >> k;
    modify(temp, l, r, -1);
    update(l, r, k);
    modify(temp, l, r, 1);
    cout << temp << '\n';
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...