Submission #218920

#	Time	Username	Problem	Language	Result	Execution time	Memory
218920		rama_pang	Two Dishes (JOI19_dishes)	C++14	74 / 100	7520 ms	196508 KiB

dishes

#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint INF = 1e16;

class SegmentTree {
 private:
  // We keep dp[n] = tree[n] + transition[n], to be able to do updates quickly
  int sz;
  vector<lint> tree;
  vector<lint> lazy_sum;
  vector<lint> lazy_max;
  vector<lint> transition;

  void Push(int n) {
    for (int c = 0; c < 2; c++) {
      tree[n * 2 + c] += lazy_sum[n];
      lazy_sum[n * 2 + c] += lazy_sum[n];
      lazy_max[n * 2 + c] += lazy_sum[n];

      tree[n * 2 + c] = max(tree[n * 2 + c], lazy_max[n]);
      lazy_max[n * 2 + c] = max(lazy_max[n * 2 + c], lazy_max[n]);

      transition[n * 2 + c] += transition[n];
    }

    lazy_max[n] = -INF;
    lazy_sum[n] = 0;
    transition[n] = 0;
  }

  void RangeSumUpdate(int n, int tl, int tr, int l, int r, lint x, bool update_tree) {
    if (r < tl || tr < l || tl > tr || l > r) return;
    if (l <= tl && tr <= r) {
      if (update_tree) {
        tree[n] += x;
        lazy_sum[n] += x;
        lazy_max[n] += x;
      } else {
        transition[n] += x;
      }
      return;
    }
    Push(n);
    int mid = (tl + tr) / 2;
    RangeSumUpdate(n * 2, tl, mid, l, r, x, update_tree);
    RangeSumUpdate(n * 2 + 1, mid + 1, tr, l, r, x, update_tree);
  }

  void RangeMaximumUpdate(int n, int tl, int tr, int l, int r, lint x) {
    if (r < tl || tr < l || tl > tr || l > r) return;
    if (l <= tl && tr <= r) {
      tree[n] = max(tree[n], x);
      lazy_max[n] = max(lazy_max[n], x);
      return;
    }
    Push(n);
    int mid = (tl + tr) / 2;
    RangeMaximumUpdate(n * 2, tl, mid, l, r, x);
    RangeMaximumUpdate(n * 2 + 1, mid + 1, tr, l, r, x); 
  }

  lint QueryTree(int n, int tl, int tr, int pos) {
    if (tl == tr) return tree[n]; // dp[] = tree[] + transition[]
    Push(n);
    int mid = (tl + tr) / 2;
    if (pos <= mid) {
      return QueryTree(n * 2, tl, mid, pos);
    } else {
      return QueryTree(n * 2 + 1, mid + 1, tr, pos);
    }
  }

  lint Query(int n, int tl, int tr, int pos) {
    if (tl == tr) return tree[n] + transition[n]; // dp[] = tree[] + transition[]
    Push(n);
    int mid = (tl + tr) / 2;
    if (pos <= mid) {
      return Query(n * 2, tl, mid, pos);
    } else {
      return Query(n * 2 + 1, mid + 1, tr, pos);
    }
  }
  

 public:
  SegmentTree(int n) : sz(n) {
    tree.assign(4 * sz, 0);
    lazy_sum.assign(4 * sz, 0);
    lazy_max.assign(4 * sz, -INF);
    transition.assign(4 * sz, 0);
  }

  void UpdateSumTree(int l, int r, lint x) { // range sum update on dp
    return RangeSumUpdate(1, 0, sz - 1, l, r, x, true);
  }

  void UpdateTransition(int l, int r, lint x) { // range sum update on transition
    return RangeSumUpdate(1, 0, sz - 1, l, r, x, false);
  }

  void UpdateMaximumTree(int l, int r, lint x) { // dp[k] = max(dp[k], transition[k] + x), x = dp[0], for all nodes
    return RangeMaximumUpdate(1, 0, sz - 1, l, r, x);
  }

  lint QueryTree(int pos) {
    return QueryTree(1, 0, sz - 1, pos);
  }

  lint Query(int pos) {
    return Query(1, 0, sz - 1, pos);
  }
};

int N, M;
vector<int> X; // X[i] = maximum index j, such that A[1] + A[2] + ... + A[i] + B[1] + B[2] + ... + B[j] <= S[i]
vector<int> Y; // Y[j] = maximum index i, such that A[1] + A[2] + ... + A[i] + B[1] + B[2] + ... + B[j] <= T[j]
vector<int> P;
vector<int> Q;

lint NaiveDP(bool dbg = false) {
  vector<vector<lint>> dp(N + 1, vector<lint>(M + 1, -INF));
  dp[0][0] = 0;
  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= M; j++) {
      if (j < M) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + (i <= Y[j + 1] ? Q[j + 1] : 0));
      if (i < N) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + (j <= X[i + 1] ? P[i + 1] : 0));
    }
  }

  if (dbg) {
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= M; j++) {
        cout << dp[i][j] << " \n"[j == M];
      }
    }
  }

  return dp[N][M];
}

lint SegmentTreeDP() {
  SegmentTree seg(M + 1);
  vector<vector<int>> deactivate(N + 1); // deactivate Q[j] at row i

  for (int j = 1; j <= M; j++) {
    if (0 <= Y[j]) {
      seg.UpdateTransition(j, M, Q[j]);
      deactivate[Y[j]].emplace_back(j);
    }
  }

  for (int i = 0; i <= N; i++) {
    seg.UpdateSumTree(0, X[i], P[i]);
    seg.UpdateMaximumTree(X[i] + 1, M, seg.QueryTree(X[i])); // maintain monotonicity

    sort(begin(deactivate[i]), end(deactivate[i]));
    for (auto j : deactivate[i]) {
      seg.UpdateTransition(j, M, -Q[j]);
      seg.UpdateSumTree(j, M, Q[j]);
    }
    
    for (auto j : deactivate[i]) {
      // make tree[] monotone again, by range maximum update on tree. 
      // This simulates the transition dp[i][j + 1] from dp[i][j]
      // As only the values [j + 1, M] changes, we only need to compare
      // it with the value at [j].
      seg.UpdateMaximumTree(j, M, seg.QueryTree(j - 1));
    }
  }

  return seg.Query(M);
}

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M;

  vector<lint> A(N + 1), B(M + 1);
  vector<lint> S(N + 1), T(M + 1);

  P.resize(N + 1), Q.resize(M + 1);
  X.resize(N + 1), Y.resize(M + 1);

  for (int i = 1; i <= N; i++) {
    cin >> A[i] >> S[i] >> P[i];
    A[i] += A[i - 1];
  }

  for (int i = 1; i <= M; i++) {
    cin >> B[i] >> T[i] >> Q[i];
    B[i] += B[i - 1];
  }

  for (int i = 0; i <= N; i++) {
    X[i] = upper_bound(begin(B), end(B), S[i] - A[i]) - begin(B) - 1;
  }

  for (int i = 0; i <= M; i++) {
    Y[i] = upper_bound(begin(A), end(A), T[i] - B[i]) - begin(A) - 1;
  }
}

int main() {
  Read();
  cout << SegmentTreeDP() << "\n";
  return 0;
}

• 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