Submission #1189530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189530		avighna	Two Dishes (JOI19_dishes)	C++20	0 / 100	531 ms	46176 KiB

dishes

#include <bits/stdc++.h>

#include <algorithm>
#include <limits>
#include <vector>

template <typename T> struct LazySegmentTree {
  struct Node {
    T mx, mn, secln;
    int cntmn;
    T add;
  };

  int n;
  std::vector<Node> st;
  static constexpr T INF = std::numeric_limits<T>::max();

  LazySegmentTree(int _n) : n(1) {
    while (n < _n)
      n <<= 1;
    st.assign(2 * n, {-INF, INF, INF, 0, 0});
  }

  void set(int i, T v) {
    int p = i + n;
    st[p] = {v, v, INF, 1, 0};
  }

  void build() {
    for (int p = n - 1; p > 0; --p)
      pull(p);
  }

  // ----- apply helpers -----
  void apply_add(int p, T v) {
    if (st[p].mn != INF) {
      st[p].mn += v;
      if (st[p].secln != INF)
        st[p].secln += v;
    }
    st[p].mx += v;
    st[p].add += v;
  }

  // precondition: x > st[p].mn && x < st[p].secln
  void apply_chmax(int p, T x) {
    st[p].mx = std::max(st[p].mx, x);
    st[p].mn = x;
    // secln stays the same
  }

  void push(int p) {
    for (int d = 0; d < 2; ++d) {
      int c = p << 1 | d;
      // first push down add
      if (st[p].add != 0) {
        apply_add(c, st[p].add);
      }
      // then clamp minima
      if (st[c].mn < st[p].mn) {
        apply_chmax(c, st[p].mn);
      }
    }
    st[p].add = 0;
  }

  void pull(int p) {
    const Node &L = st[p << 1], &R = st[p << 1 | 1];
    // mx
    st[p].mx = std::max(L.mx, R.mx);
    // mn & secln & cntmn
    if (L.mn < R.mn) {
      st[p].mn = L.mn;
      st[p].cntmn = L.cntmn;
      st[p].secln = std::min(L.secln, R.mn);
    } else if (L.mn > R.mn) {
      st[p].mn = R.mn;
      st[p].cntmn = R.cntmn;
      st[p].secln = std::min(L.mn, R.secln);
    } else {
      st[p].mn = L.mn;
      st[p].cntmn = L.cntmn + R.cntmn;
      st[p].secln = std::min(L.secln, R.secln);
    }
    st[p].add = 0;
  }

  // ----- range operations on [ql..qr], node p covers [l..r] -----
  void range_add(int p, int l, int r, int ql, int qr, T v) {
    if (qr < l || r < ql)
      return;
    if (ql <= l && r <= qr) {
      apply_add(p, v);
      return;
    }
    push(p);
    int m = (l + r) >> 1;
    range_add(p << 1, l, m, ql, qr, v);
    range_add(p << 1 | 1, m + 1, r, ql, qr, v);
    pull(p);
  }

  void range_chmax(int p, int l, int r, int ql, int qr, T x) {
    if (qr < l || r < ql || x <= st[p].mn)
      return;
    if (ql <= l && r <= qr && x < st[p].secln) {
      apply_chmax(p, x);
      return;
    }
    push(p);
    int m = (l + r) >> 1;
    range_chmax(p << 1, l, m, ql, qr, x);
    range_chmax(p << 1 | 1, m + 1, r, ql, qr, x);
    pull(p);
  }

  T range_max(int p, int l, int r, int ql, int qr) {
    if (qr < l || r < ql)
      return -INF;
    if (ql <= l && r <= qr) {
      return st[p].mx;
    }
    push(p);
    int m = (l + r) >> 1;
    return std::max(range_max(p << 1, l, m, ql, qr),
                    range_max(p << 1 | 1, m + 1, r, ql, qr));
  }

  // ----- public API -----
  void add(int l, int r, T v) { range_add(1, 0, n - 1, l, r, v); }
  void chmax(int l, int r, T x) { range_chmax(1, 0, n - 1, l, r, x); }
  T query(int l, int r) { return range_max(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]});
  }

  LazySegmentTree<long long> st(m + 1);
  for (int i = 0; i <= m; ++i) {
    st.set(i, 0);
  }
  st.build();
  // st.chmax(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.chmax(0, y, st.query(y, y));
    }
  }
  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