Submission #1189499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189499		avighna	Two Dishes (JOI19_dishes)	C++20	0 / 100	10089 ms	56908 KiB

dishes

#include <bits/stdc++.h>

// lazy operations => add to range, max to range
// query => return max in range
template <typename T> class LazySegmentTree {
private:
  const T max_idt = -1e15;

public:
  std::vector<T> seg, lazy_add, lazy_max;
  int n;

  LazySegmentTree(int n) : n(n) {
    seg.resize(4 * n, max_idt);
    lazy_add.resize(8 * n, 0);
    lazy_max.resize(8 * n, max_idt);
  }

  void lazy_update(int v) {
    // for max
    if (lazy_max[v] != max_idt) {
      lazy_add[2 * v] = lazy_add[2 * v + 1] = 0;
      seg[v] = std::max(seg[v], lazy_max[v]);
      lazy_max[2 * v] = std::max(lazy_max[2 * v], lazy_max[v]);
      lazy_max[2 * v + 1] = std::max(lazy_max[2 * v + 1], lazy_max[v]);
      lazy_max[v] = max_idt;
    }

    // for add
    seg[v] += lazy_add[v];
    lazy_add[2 * v] += lazy_add[v];
    lazy_add[2 * v + 1] += lazy_add[v];
    lazy_add[v] = 0;
  }

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

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

  T query(int v, int tl, int tr, int l, int r) {
    lazy_update(v);
    if (tr < l or r < tl) {
      return max_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() {
  // LazySegmentTree<long long> tree(5);
  // tree.set_max(0, 4, 0);
  // // for (int i = 0; i < 5; ++i) {
  // //   std::cout << tree.query(i, i) << " \n"[i == 4];
  // // }
  // tree.add(0, 2, 3);
  // // for (int i = 0; i < 5; ++i) {
  // //   std::cout << tree.query(i, i) << " \n"[i == 4];
  // // }
  // tree.set_max(2, 3, 4);
  // tree.add(2, 3, 1);
  // // for (int i = 0; i < 5; ++i) {
  // //   std::cout << tree.query(i, i) << " \n"[i == 4];
  // // }
  // tree.set_max(1, 2, 4);
  // for (int i = 0; i < 5; ++i) {
  //   std::cout << tree.query(i, i) << " \n"[i == 4];
  // }
  // return 0;

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

  std::vector<long long> p_a(n), p_b(m);
  std::partial_sum(a.begin(), a.end(), p_a.begin());
  std::partial_sum(b.begin(), b.end(), p_b.begin());

  // pts_y[some x coord] = vector of {y, val}
  std::vector<std::vector<std::pair<int, int>>> pts_y(n + 1);

  for (int i = 0; i < n; ++i) {
    // for i, what is the max j such that we still get p[i] points?
    // basically, p_a[i] + p_b[j] <= s[i]
    // ==> min j such that p_a[i] + p_b[j] > s[i], then -1
    // p_b[j] > s[i] - p_a[i]
    auto it = std::upper_bound(p_b.begin(), p_b.end(), s[i] - p_a[i]);
    // point is (i, max_j). we get p[i] points if we reach i before max_j. so
    // we're above our path.

    // the way to gurantee that we're below the path is to pass through point (i
    // - 1, max_j + 1) (and have this below our path). all other points that
    // gurantee this can be reached from this one. so we can just assign a score
    // of -p[i] to this.
    pts_y[std::max(0, i - 1)].push_back({it - p_b.begin(), -p[i]});
  }
  for (int j = 0; j < m; ++j) {
    // for j, what is the max i such that we still get q[j] points?
    // p_b[j] + p_a[i] <= t[j]
    // ==> min i such that p_b[j] + p_a[i] > t[j]
    // p_a[i] > t[j] - p_b[j]
    auto it = std::upper_bound(p_a.begin(), p_a.end(), t[j] - p_b[j]);
    if (it == p_a.begin()) {
      continue;
    }
    // point is (max_i, j). we get q[j] points if we reach j before max_i. so we
    // reach max_i after j. so we're below our path.
    pts_y[it - p_a.begin() - 1].push_back({j, q[j]});
  }

  // std::cout << "points:\n";

  LazySegmentTree<long long> st(m + 1);
  st.set_max(0, m, 0);
  for (int i = n; i >= 0; --i) {
    std::sort(pts_y[i].rbegin(), pts_y[i].rend());
    // dp[i] = dp[i + 1] + [new points at x=i]
    for (auto &[y, val] : pts_y[i]) {
      st.add(y, m, val);
    }
    // dp[i][j] = max(dp[i][j], dp[i][j + 1])
    for (auto &[y, val] : pts_y[i]) {
      st.set_max(0, y, st.query(y, y));
    }
    // std::cout << "dp array: ";
    for (int j = 0; j <= m; ++j) {
      st.query(j, j);
    }
    // std::cout << '\n';
  }
  std::cout << std::accumulate(p.begin(), p.end(), 0LL) + st.query(0, 0)
            << '\n';
}

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