oj.uz

Submission #218920

# Submission time Handle Problem Language Result Execution time Memory
218920 2020-04-03T07:25:22 Z rama_pang Two Dishes (JOI19_dishes) C++14
74 / 100
 7520 ms 196508 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 39932 KB Output is correct
2 Correct 982 ms 39652 KB Output is correct
3 Correct 1056 ms 37972 KB Output is correct
4 Correct 802 ms 39524 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 1038 ms 37644 KB Output is correct
7 Correct 541 ms 31544 KB Output is correct
8 Correct 104 ms 9408 KB Output is correct
9 Correct 1058 ms 38016 KB Output is correct
10 Correct 972 ms 42364 KB Output is correct
11 Correct 1008 ms 38012 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 288 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 288 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 8 ms 768 KB Output is correct
18 Correct 8 ms 760 KB Output is correct
19 Correct 10 ms 768 KB Output is correct
20 Correct 8 ms 768 KB Output is correct
21 Correct 10 ms 768 KB Output is correct
22 Correct 9 ms 768 KB Output is correct
23 Correct 9 ms 896 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 288 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 8 ms 768 KB Output is correct
18 Correct 8 ms 760 KB Output is correct
19 Correct 10 ms 768 KB Output is correct
20 Correct 8 ms 768 KB Output is correct
21 Correct 10 ms 768 KB Output is correct
22 Correct 9 ms 768 KB Output is correct
23 Correct 9 ms 896 KB Output is correct
24 Correct 1431 ms 36988 KB Output is correct
25 Correct 1053 ms 37884 KB Output is correct
26 Correct 733 ms 37116 KB Output is correct
27 Correct 1029 ms 42364 KB Output is correct
28 Correct 1024 ms 38012 KB Output is correct
29 Correct 1020 ms 38012 KB Output is correct
30 Correct 1223 ms 40016 KB Output is correct
31 Correct 573 ms 31132 KB Output is correct
32 Correct 102 ms 9408 KB Output is correct
33 Correct 852 ms 38340 KB Output is correct
34 Correct 1108 ms 37660 KB Output is correct
35 Correct 1151 ms 40060 KB Output is correct
36 Correct 1153 ms 40060 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 288 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 8 ms 768 KB Output is correct
18 Correct 8 ms 760 KB Output is correct
19 Correct 10 ms 768 KB Output is correct
20 Correct 8 ms 768 KB Output is correct
21 Correct 10 ms 768 KB Output is correct
22 Correct 9 ms 768 KB Output is correct
23 Correct 9 ms 896 KB Output is correct
24 Correct 1431 ms 36988 KB Output is correct
25 Correct 1053 ms 37884 KB Output is correct
26 Correct 733 ms 37116 KB Output is correct
27 Correct 1029 ms 42364 KB Output is correct
28 Correct 1024 ms 38012 KB Output is correct
29 Correct 1020 ms 38012 KB Output is correct
30 Correct 1223 ms 40016 KB Output is correct
31 Correct 573 ms 31132 KB Output is correct
32 Correct 102 ms 9408 KB Output is correct
33 Correct 852 ms 38340 KB Output is correct
34 Correct 1108 ms 37660 KB Output is correct
35 Correct 1151 ms 40060 KB Output is correct
36 Correct 1153 ms 40060 KB Output is correct
37 Correct 725 ms 36988 KB Output is correct
38 Correct 1093 ms 42492 KB Output is correct
39 Correct 957 ms 42492 KB Output is correct
40 Correct 963 ms 42364 KB Output is correct
41 Correct 4 ms 384 KB Output is correct
42 Correct 1245 ms 40036 KB Output is correct
43 Correct 870 ms 38236 KB Output is correct
44 Correct 1143 ms 37368 KB Output is correct
45 Correct 1186 ms 40060 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 288 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 8 ms 768 KB Output is correct
18 Correct 8 ms 760 KB Output is correct
19 Correct 10 ms 768 KB Output is correct
20 Correct 8 ms 768 KB Output is correct
21 Correct 10 ms 768 KB Output is correct
22 Correct 9 ms 768 KB Output is correct
23 Correct 9 ms 896 KB Output is correct
24 Correct 1431 ms 36988 KB Output is correct
25 Correct 1053 ms 37884 KB Output is correct
26 Correct 733 ms 37116 KB Output is correct
27 Correct 1029 ms 42364 KB Output is correct
28 Correct 1024 ms 38012 KB Output is correct
29 Correct 1020 ms 38012 KB Output is correct
30 Correct 1223 ms 40016 KB Output is correct
31 Correct 573 ms 31132 KB Output is correct
32 Correct 102 ms 9408 KB Output is correct
33 Correct 852 ms 38340 KB Output is correct
34 Correct 1108 ms 37660 KB Output is correct
35 Correct 1151 ms 40060 KB Output is correct
36 Correct 1153 ms 40060 KB Output is correct
37 Correct 725 ms 36988 KB Output is correct
38 Correct 1093 ms 42492 KB Output is correct
39 Correct 957 ms 42492 KB Output is correct
40 Correct 963 ms 42364 KB Output is correct
41 Correct 4 ms 384 KB Output is correct
42 Correct 1245 ms 40036 KB Output is correct
43 Correct 870 ms 38236 KB Output is correct
44 Correct 1143 ms 37368 KB Output is correct
45 Correct 1186 ms 40060 KB Output is correct
46 Correct 4091 ms 169152 KB Output is correct
47 Correct 6070 ms 196508 KB Output is correct
48 Correct 5349 ms 196484 KB Output is correct
49 Correct 5331 ms 196392 KB Output is correct
50 Correct 7520 ms 184728 KB Output is correct
51 Correct 5275 ms 174716 KB Output is correct
52 Correct 6584 ms 162364 KB Output is correct
53 Correct 7329 ms 184168 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 39932 KB Output is correct
2 Correct 982 ms 39652 KB Output is correct
3 Correct 1056 ms 37972 KB Output is correct
4 Correct 802 ms 39524 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 1038 ms 37644 KB Output is correct
7 Correct 541 ms 31544 KB Output is correct
8 Correct 104 ms 9408 KB Output is correct
9 Correct 1058 ms 38016 KB Output is correct
10 Correct 972 ms 42364 KB Output is correct
11 Correct 1008 ms 38012 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 288 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 4 ms 384 KB Output is correct
26 Correct 4 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 8 ms 768 KB Output is correct
29 Correct 8 ms 760 KB Output is correct
30 Correct 10 ms 768 KB Output is correct
31 Correct 8 ms 768 KB Output is correct
32 Correct 10 ms 768 KB Output is correct
33 Correct 9 ms 768 KB Output is correct
34 Correct 9 ms 896 KB Output is correct
35 Correct 1431 ms 36988 KB Output is correct
36 Correct 1053 ms 37884 KB Output is correct
37 Correct 733 ms 37116 KB Output is correct
38 Correct 1029 ms 42364 KB Output is correct
39 Correct 1024 ms 38012 KB Output is correct
40 Correct 1020 ms 38012 KB Output is correct
41 Correct 1223 ms 40016 KB Output is correct
42 Correct 573 ms 31132 KB Output is correct
43 Correct 102 ms 9408 KB Output is correct
44 Correct 852 ms 38340 KB Output is correct
45 Correct 1108 ms 37660 KB Output is correct
46 Correct 1151 ms 40060 KB Output is correct
47 Correct 1153 ms 40060 KB Output is correct
48 Correct 725 ms 36988 KB Output is correct
49 Correct 1093 ms 42492 KB Output is correct
50 Correct 957 ms 42492 KB Output is correct
51 Correct 963 ms 42364 KB Output is correct
52 Correct 4 ms 384 KB Output is correct
53 Correct 1245 ms 40036 KB Output is correct
54 Correct 870 ms 38236 KB Output is correct
55 Correct 1143 ms 37368 KB Output is correct
56 Correct 1186 ms 40060 KB Output is correct
57 Incorrect 752 ms 34172 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 982 ms 39932 KB Output is correct
2 Correct 982 ms 39652 KB Output is correct
3 Correct 1056 ms 37972 KB Output is correct
4 Correct 802 ms 39524 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 1038 ms 37644 KB Output is correct
7 Correct 541 ms 31544 KB Output is correct
8 Correct 104 ms 9408 KB Output is correct
9 Correct 1058 ms 38016 KB Output is correct
10 Correct 972 ms 42364 KB Output is correct
11 Correct 1008 ms 38012 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 288 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 4 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 4 ms 384 KB Output is correct
26 Correct 4 ms 384 KB Output is correct
27 Correct 4 ms 384 KB Output is correct
28 Correct 8 ms 768 KB Output is correct
29 Correct 8 ms 760 KB Output is correct
30 Correct 10 ms 768 KB Output is correct
31 Correct 8 ms 768 KB Output is correct
32 Correct 10 ms 768 KB Output is correct
33 Correct 9 ms 768 KB Output is correct
34 Correct 9 ms 896 KB Output is correct
35 Correct 1431 ms 36988 KB Output is correct
36 Correct 1053 ms 37884 KB Output is correct
37 Correct 733 ms 37116 KB Output is correct
38 Correct 1029 ms 42364 KB Output is correct
39 Correct 1024 ms 38012 KB Output is correct
40 Correct 1020 ms 38012 KB Output is correct
41 Correct 1223 ms 40016 KB Output is correct
42 Correct 573 ms 31132 KB Output is correct
43 Correct 102 ms 9408 KB Output is correct
44 Correct 852 ms 38340 KB Output is correct
45 Correct 1108 ms 37660 KB Output is correct
46 Correct 1151 ms 40060 KB Output is correct
47 Correct 1153 ms 40060 KB Output is correct
48 Correct 725 ms 36988 KB Output is correct
49 Correct 1093 ms 42492 KB Output is correct
50 Correct 957 ms 42492 KB Output is correct
51 Correct 963 ms 42364 KB Output is correct
52 Correct 4 ms 384 KB Output is correct
53 Correct 1245 ms 40036 KB Output is correct
54 Correct 870 ms 38236 KB Output is correct
55 Correct 1143 ms 37368 KB Output is correct
56 Correct 1186 ms 40060 KB Output is correct
57 Correct 4091 ms 169152 KB Output is correct
58 Correct 6070 ms 196508 KB Output is correct
59 Correct 5349 ms 196484 KB Output is correct
60 Correct 5331 ms 196392 KB Output is correct
61 Correct 7520 ms 184728 KB Output is correct
62 Correct 5275 ms 174716 KB Output is correct
63 Correct 6584 ms 162364 KB Output is correct
64 Correct 7329 ms 184168 KB Output is correct
65 Incorrect 752 ms 34172 KB Output isn't correct
66 Halted 0 ms 0 KB -