제출 #1189699

#제출 시각아이디문제언어결과실행 시간메모리
1189699avighnaTwo Dishes (JOI19_dishes)C++20
100 / 100
4578 ms284144 KiB
#include <bits/stdc++.h>

template <typename T> class LazySegmentTree {
public:
  class Operation { // (sum, max)
  public:
    T sum, max;
    Operation operator+(const Operation &y) {
      return Operation({sum + y.sum, std::max(max + y.sum, y.max)});
    }
  };

  std::vector<T> seg;
  std::vector<Operation> lazy;
  constexpr static T idt = std::numeric_limits<T>::min() >> 4;
  int n;

  LazySegmentTree(int n) : n(n) {
    seg.resize(4 * n, idt);
    lazy.resize(8 * n, {0, idt});
  }

  void lazy_update(int v) {
    seg[v] = std::max(seg[v] + lazy[v].sum, lazy[v].max);
    lazy[2 * v] = lazy[2 * v] + lazy[v];
    lazy[2 * v + 1] = lazy[2 * v + 1] + lazy[v];
    lazy[v] = {0, idt};
  }

  void update(int v, int tl, int tr, int l, int r, Operation op) {
    lazy_update(v);
    if (tr < l or r < tl) {
      return;
    }
    if (l <= tl and tr <= r) {
      lazy[v] = lazy[v] + op;
      lazy_update(v);
      return;
    }
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, r, op);
    update(2 * v + 1, tm + 1, tr, l, r, op);
    seg[v] = std::max(seg[2 * v], seg[2 * v + 1]);
  }
  void set_max(int l, int r, T x) {
    update(1, 0, n - 1, l, r, Operation({0, x}));
  }
  void add(int l, int r, T del) {
    update(1, 0, n - 1, l, r, Operation({del, idt}));
  }

  T query(int v, int tl, int tr, int l, int r) {
    lazy_update(v);
    if (tr < l or r < tl) {
      return idt;
    }
    if (l <= tl and tr <= r) {
      return seg[v];
    }
    int tm = (tl + tr) / 2;
    return std::max(query(2 * v, tl, tm, l, r),
                    query(2 * v + 1, tm + 1, tr, l, r));
  }
  T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<long long> a(n + 1), s(n + 1), p(n + 1);
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i] >> s[i] >> p[i];
  }
  std::vector<long long> b(m + 1), t(m + 1), q(m + 1);
  for (int i = 1; i <= m; ++i) {
    std::cin >> b[i] >> t[i] >> q[i];
  }

  std::vector<long long> p_a(n + 1), p_b(m + 1);
  std::partial_sum(a.begin(), a.end(), p_a.begin());
  std::partial_sum(b.begin(), b.end(), p_b.begin());
  std::vector<std::vector<std::pair<int, int>>> pts_y(n + 1);
  long long init = 0;
  for (int i = 1; i <= n; ++i) {
    if (p_a[i] > s[i]) {
      continue;
    }
    if (p_a[i] + p_b.back() <= s[i]) {
      init += p[i];
      continue;
    }
    init += p[i];
    auto it = std::upper_bound(p_b.begin(), p_b.end(), s[i] - p_a[i]);
    pts_y[i - 1].push_back({it - p_b.begin(), -p[i]});
  }
  for (int j = 1; j <= m; ++j) {
    if (p_b[j] > t[j]) {
      continue;
    }
    if (p_b[j] + p_a.back() <= t[j]) {
      init += q[j];
      continue;
    }
    auto it = std::upper_bound(p_a.begin(), p_a.end(), t[j] - p_b[j]);
    if (it == p_a.begin()) {
      continue;
    }
    pts_y[it - p_a.begin() - 1].push_back({j, q[j]});
  }

  LazySegmentTree<long long> st(m + 1);
  st.set_max(0, m, 0);
  for (int i = n; i >= 0; --i) {
    for (auto &[y, val] : pts_y[i]) {
      st.add(y, m, val);
    }
    for (auto &[y, val] : pts_y[i]) {
      st.set_max(0, y, st.query(y, y));
    }
  }
  std::cout << init + st.query(0, 0) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...