Submission #520700

#	Time	Username	Problem	Language	Result	Execution time	Memory
520700		Alex_tz307	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	134 ms	11560 KiB

foehn_phenomena

#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;
}

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