Submission #981012

#	Time	Username	Problem	Language	Result	Execution time	Memory
981012		kilkuwu	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	267 ms	23380 KiB

foehn_phenomena

#include <bits/stdc++.h>

#define nl '\n'

template <typename T, typename L, typename F = std::plus<T>>
struct SegmentTree {
  int n;
  std::vector<T> tree;
  std::vector<L> lazy;

  SegmentTree(int _n) : n(_n), tree(2 * n - 1), lazy(2 * n - 1) {}

  template <typename Vec>
  void build(int x, int l, int r, const Vec& v) {
    if (l == r - 1) {
      tree[x] = T::from_value(v[l]);
      return;
    }

    int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
    build(y, l, m, v);
    build(z, m, r, v);
    tree[x] = F()(tree[y], tree[z]);
  } 

  template <typename Vec> 
  SegmentTree(const Vec& v) : SegmentTree(static_cast<int>(v.size())) {
    build(0, 0, n, v);
  }

  inline void apply(int x, const L& t) {
    tree[x].apply(t);
    lazy[x].apply(t);
  }

  inline void push(int x, int y, int z) {
    apply(y, lazy[x]);
    apply(z, lazy[x]);
    lazy[x] = L();
  }

  inline void pull(int x, int y, int z) {
    tree[x] = F()(tree[y], tree[z]);
  }

  void modify(int x, int l, int r, int p, const T& v) {
    if (l == r - 1) {
      tree[x] = v;
      return;
    }
    int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
    push(x, y, z);
    if (p < m)
      modify(y, l, m, p, v);
    else
      modify(z, m, r, p, v);
    pull(x, y, z);
  }

  void range_apply(int x, int l, int r, int ql, int qr, const L& t) {
    if (ql <= l && r <= qr) {
      apply(x, t);
      return;
    }
    int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
    push(x, y, z);
    if (m > ql) range_apply(y, l, m, ql, qr, t);
    if (m < qr) range_apply(z, m, r, ql, qr, t);
    pull(x, y, z);
  }

  T range_query(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
      return tree[x];
    }
    int m = (l + r) / 2, y = x + 1, z = x + (m - l) * 2;
    push(x, y, z);
    if (m <= ql) return range_query(z, m, r, ql, qr);
    if (m >= qr) return range_query(y, l, m, ql, qr);
    return F()(range_query(y, l, m, ql, qr), range_query(z, m, r, ql, qr));
  }

  inline void modify(int p, const T& v) {
    assert(0 <= p && p < n);
    modify(0, 0, n, p, v);
  }
  // NOTE: [l, r)
  inline void range_apply(int l, int r, const L& t) {
    assert(0 <= l && l < r && r <= n);
    range_apply(0, 0, n, l, r, t);
  }
  // NOTE: [l, r)
  inline T range_query(int l, int r) {
    assert(0 <= l && l < r && r <= n);
    return range_query(0, 0, n, l, r);
  }
};

struct Tag {
  int64_t x;
  
  inline void apply(const Tag& t) {
    x += t.x;
  }
};

int S, T;

struct Info {
  int64_t l, r;
  int64_t delta;
  // implement from_value<T> to allow build(vector<T>)
  static Info from_value(int x) {
    return {x, x, 0};
  }

  inline void apply(const Tag& t) {
    l += t.x;
    r += t.x;
  }

  friend Info operator+(const Info& l, const Info& r) {
    int64_t ll = l.l;
    int64_t rr = r.r;
    int64_t delta = l.delta;
    if (l.r < r.l) {
      delta -= S * (r.l - l.r);
    } else {
      delta += T * (l.r - r.l);
    }
    delta += r.delta;
    return {ll, rr, delta};
  }
};

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int N, Q;
  std::cin >> N >> Q >> S >> T;

  std::vector<int> A(N + 1);
  for (int i = 0; i <= N; i++) {
    std::cin >> A[i];
  }

  SegmentTree<Info, Tag> tree(A);


  while (Q--) {
    int l, r, x;
    std::cin >> l >> r >> x;
    tree.range_apply(l, r + 1, {x});
    std::cout << tree.range_query(0, N + 1).delta << nl;
  }
}

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