Submission #1084049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084049		May27_th	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	30 / 100	659 ms	34128 KiB

foehn_phenomena

#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
struct Tree{
  int n;
  vector<int64_t>lazy;
  vector<int64_t>st;
  Tree(int _n, int64_t _v): n(_n), st(_n * 4, _v), lazy(_n * 4, _v){};
  void push(int id){
    int64_t add = lazy[id];
    lazy[id * 2] += add, st[id * 2] += add;
    lazy[id * 2 + 1] += add, st[id * 2 + 1] += add;
    lazy[id] = 0;
  }
  void update(int id, int l, int r, int u, int v, int64_t val){
    if (v < l || u > r) return;
    if (u <= l && r <= v) {
      st[id] += val;
      lazy[id] += val;
      return;
    }
    push(id);
    int mid = (l + r)/2;
    update(id * 2, l, mid, u, v, val);
    update(id * 2 + 1, mid + 1, r, u, v, val);
    st[id] = st[id * 2] + st[id * 2 + 1];
  }
  i64 get(int id, int l, int r, int u, int v) {
    if (v < l || u > r) return 0;
    if (u <= l && r <= v) return st[id];
    push(id);
    int mid = (l + r)/2;
    return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
  }
  int find(int id, int l, int r, int u, int v){
    if (v < l || u > r) return 0;
    if (st[id] > 0) return 0;
    if (l == r) return l;
    push(id);
    int mid = (l + r)/2;
    int rg = find(id * 2 + 1, mid + 1, r, u, v);
    if (rg != 0) return rg;
    return find(id * 2, l, mid, u, v);
  }
};
void Solve(void) {
  int N, Q, S, T; cin >> N >> Q >> S >> T;
  i64 pref = 0;
  Tree tot(N + 4, 0);
  Tree a(N + 4, 0);
  for (int i = 0; i <= N; i ++) {
    int x; cin >> x;
    a.update(1, 0, N, i, i, x);
  }
  for (int i = 0; i < N; i ++) {
    int cur = a.get(1, 0, N, i, i);
    int nxt = a.get(1, 0, N, i + 1, i + 1);
    // cout << cur << " " << nxt << "\n";
    if (cur < nxt) {
      pref = pref - 1LL * (nxt - cur) * S;
    } else {
      pref = pref + 1LL * (cur - nxt) * T;
    }
    tot.update(1, 1, N, i + 1, i + 1, pref);
    // cout << i + 1 << " " << pref << "\n";
  }  

  auto Dec = [&](int l, int r) {
    int al = a.get(1, 0, N, l, l);
    int preval = a.get(1, 0, N, l - 1, l - 1);
    if (preval < al) {
      // cur = cur - 1LL * (nxt - cur) * S;
      tot.update(1, 1, N, l, r, +1LL * (al - preval) * S);
    } else {
      tot.update(1, 1, N, l, r, -1LL * (preval - al) * T);
    }
  };

  auto Add = [&](int l, int r) {
    int al = a.get(1, 0, N, l, l);
    int preval = a.get(1, 0, N, l - 1, l - 1);
    if (preval < al) {
      tot.update(1, 1, N, l, r, -1LL * (al - preval) * S);
    } else {
      tot.update(1, 1, N, l, r, +1LL * (preval - al) * T);
    }
  };

  while (Q --) {
    int l, r, x; cin >> l >> r >> x;
    Dec(l, N);
    if (r < N) Dec(r + 1, N);

    a.update(1, 0, N, l, r, x);

    Add(l, N);
    if (r < N) Add(r + 1, N);
    // for (int i = 1; i <= N; i ++) {
    //   cout << tot.get(1, 1, N, i, i) << " ";
    // } cout << "\n";
    cout << tot.get(1, 1, N, N, N) << "\n";
  }
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int Tests = 1; // cin >> Tests; 
  while (Tests --) {
    Solve();    
  }
}

Compilation message (stderr)

foehn_phenomena.cpp: In constructor 'Tree::Tree(int, int64_t)':
foehn_phenomena.cpp:12:18: warning: 'Tree::st' will be initialized after [-Wreorder]
   12 |   vector<int64_t>st;
      |                  ^~
foehn_phenomena.cpp:11:18: warning:   'std::vector<long int> Tree::lazy' [-Wreorder]
   11 |   vector<int64_t>lazy;
      |                  ^~~~
foehn_phenomena.cpp:13:3: warning:   when initialized here [-Wreorder]
   13 |   Tree(int _n, int64_t _v): n(_n), st(_n * 4, _v), lazy(_n * 4, _v){};
      |   ^~~~

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