Submission #1189702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189702		avighna	Two Dishes (JOI19_dishes)	C++20	74 / 100	4687 ms	284000 KiB

dishes

#include <bits/stdc++.h>

template <typename T> class LazySegmentTree {
private:
  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;

public:
  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), b(m + 1), t(m + 1),
      q(m + 1), p_a(n + 1), p_b(m + 1);
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i] >> s[i] >> p[i];
  }
  for (int i = 1; i <= m; ++i) {
    std::cin >> b[i] >> t[i] >> q[i];
  }
  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;
    }
    init += p[i];
    if (p_a[i] + p_b.back() <= s[i]) {
      continue;
    }
    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]);
    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);
      st.set_max(0, y, st.query(y, y));
    }
  }
  std::cout << st.query(0, 0) + init << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9