Submission #307596

#	Time	Username	Problem	Language	Result	Execution time	Memory
307596		milleniumEeee	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	524 ms	13688 KiB

foehn_phenomena

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

const int MAXN = (int)2e5 + 5;

int a[MAXN];
int tree[MAXN * 4], lazy[MAXN * 4];
int n, q, s, t;

void build(int v, int tl, int tr) {
  if (tl == tr) {
    tree[v] = a[tl];
    return;
  }
  int mid = (tl + tr) >> 1;
  build(v + v, tl, mid);
  build(v + v + 1, mid + 1, tr);
}

void push(int v, int tl, int tr) {
  if (!lazy[v]) { 
    return;
  }
  if (tl != tr) {
    lazy[v + v] += lazy[v];
    lazy[v + v + 1] += lazy[v];
  } else {
    tree[v] += lazy[v];
  }
  lazy[v] = 0;
}

void upd(int l, int r, int val, int v, int tl, int tr) {
  push(v, tl, tr);
  if (l <= tl && tr <= r) {
    lazy[v] = val;
    push(v, tl, tr);
    return;
  }
  if (l > tr || tl > r) {
    return;
  }
  int mid = (tl + tr) >> 1;
  upd(l, r, val, v + v, tl, mid);
  upd(l, r, val, v + v + 1, mid + 1, tr);
}

int get(int pos, int v, int tl, int tr) {
  if (pos == 0) { // case
    return 0;
  }
  
  push(v, tl, tr);
  if (tl == tr) {
    return tree[v];
  }
  int mid = (tl + tr) >> 1;
  if (pos <= mid) {
    return get(pos, v + v, tl, mid);
  } else {
    return get(pos, v + v + 1, mid + 1, tr);
  }
}

int calc(int i, int j) { // i < j
  int x = get(i, 1, 1, n);
  int y = get(j, 1, 1, n);
  int diff = abs(x - y);
  if (x < y) {
    return -(diff * s);
  } else {
    return diff * t;
  }
}


signed main() {
  cin >> n >> q >> s >> t;
  for (int i = 0; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  build(1, 1, n);
  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans += calc(i, i + 1);
  }
  while (q--) {
    int l, r, val;
    scanf("%lld %lld %lld", &l, &r, &val);
    if (l - 1 >= 0) {
      ans -= calc(l - 1, l);
    }
    if (r + 1 <= n) {
      ans -= calc(r, r + 1);
    }
    upd(l, r, val, 1, 1, n);
    if (l - 1 >= 0) {
      ans += calc(l - 1, l);
    }
    if (r + 1 <= n) {
      ans += calc(r, r + 1);
    }
    printf("%lld\n", ans);
  }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%lld", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
foehn_phenomena.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |     scanf("%lld %lld %lld", &l, &r, &val);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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