Submission #783474

#	Time	Username	Problem	Language	Result	Execution time	Memory
783474		makanhulia	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	368 ms	15592 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;

ll n, q, s, t, ans = 0, arr[MAXN], seg[4*MAXN];
// Segtree nyimpen difference

void build(ll pos, ll l, ll r) {
  if (l == r)
  {
    seg[pos] = 0;
    return ;
  }

  ll mid = (l+r)/2;
  build(pos*2, l, mid);
  build(pos*2+1, mid+1, r);
  seg[pos] = 0;
}  

void update(ll pos, ll l, ll r, ll a, ll b, ll x){
  if (l > b || r < a)
  {
    return ;
  }

  if (seg[pos])
  {
    // Kalo ga leaf
    if (l != r)
    {
      seg[pos*2] += seg[pos];
      seg[pos*2+1] += seg[pos];
      seg[pos] = 0;
    }
  }

  if (a <= l && r <= b)
  {
    seg[pos] += x;
    return ;
  }

  ll mid = (l+r)/2;
  update(pos*2, l, mid, a, b, x);
  update(pos*2+1, mid+1, r, a, b, x);
}

ll query(ll pos, ll l, ll r, ll x) {
  if (l > x || r < x)
  {
    return 0;
  }

  if (seg[pos])
  {
    // Kalo ga leaf
    if (l != r)
    {
      seg[pos*2] += seg[pos];
      seg[pos*2+1] += seg[pos];
      seg[pos] = 0;
    }
  }

  if (x <= l && r <= x)
  {
    ll tmp = seg[pos];
    seg[pos] = 0;
    return tmp;
  }

  ll mid = (l+r)/2;
  return query(pos*2, l, mid, x) + query(pos*2+1, mid+1, r, x);
}

ll cek(ll a, ll b) {
  if (a < b)
  {
    return (a - b) * s;
  }
  return (a - b) * t;
}

void upt(ll x) {
  if (x <= 0 || x > n)
  {
    return ;
  }

  arr[x] += query(1, 1, n, x);
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n >> q >> s >> t;
  for (int i = 0; i <= n; ++i)
  {
    cin >> arr[i];
  }

  for (int i = 1; i <= n; ++i)
  {
    ans += cek(arr[i-1], arr[i]);
  }

  build(1, 1, n);
  while(q--) {
    ll l, r, x;
    cin >> l >> r >> x;

    upt(l);
    upt(l-1);
    upt(r);
    upt(r+1);

    // cout << l << " | --";
    // cout << arr[l-1] << " " << arr[l] << "\n";

    ans -= cek(arr[l-1], arr[l]);

    if(r < n) {
      ans -= cek(arr[r], arr[r+1]);
    }

    update(1, 1, n, l, r, x);

    upt(l);
    upt(r);

    // cout << l << " | ";
    // cout << arr[l-1] << " " << arr[l] << "\n";
    ans += cek(arr[l-1], arr[l]);

    if (r < n)
    {
      ans += cek(arr[r], arr[r+1]);
    }

    cout << ans << "\n";
  }
  return 0;
}

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