oj.uz

Submission #388953

# Submission time Handle Problem Language Result Execution time Memory
388953 2021-04-13T11:17:42 Z rama_pang Bodyguard (JOI21_bodyguard) C++17
100 / 100
 9037 ms 363980 KB 
#include <bits/stdc++.h>
using namespace std;

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N, Q;
  cin >> N >> Q;

  vector<lint> T(N), A(N), B(N), C(N);
  for (int i = 0; i < N; i++) {
    cin >> T[i] >> A[i] >> B[i] >> C[i];
    T[i] *= 2; A[i] *= 2; B[i] *= 2;
  }

  vector<lint> P(Q), X(Q);
  for (int i = 0; i < Q; i++) {
    cin >> P[i] >> X[i];
    P[i] *= 2; X[i] *= 2;
  }

  // Solution:
  // In the 2D graph of position and time, the VIPs
  // are diagonal lines. We must move (diagonally)
  // s.t. maximize the sum of costs of overlapping lines.
  //
  // Rotate the lines by 45 degrees using (x + y, x - y).
  // Then, we can do coordinate compression. Since there
  // are O(N) distinct x coordinates and y coordinates,
  // we can make the DP table in O(N^2).
  //
  // For each query, assume we go rightwards (downwards is
  // symnetric). Then there are O(N) distinct y coordinates
  // we can start on, so this runs in O(Q N).  We can optimize
  // getting the answer for a query with the Convex Hull Trick.
  //
  // Time complexity: O(N^2 + Q log N).

  vector<lint> ans(Q);

  vector<lint> coords = {-INF, INF};
  vector<array<lint, 3>> query;
  vector<array<lint, 5>> lines;

  for (int i = 0; i < N; i++) {
    pair<lint, lint> st = {T[i], A[i]};
    pair<lint, lint> et = {T[i] + abs(A[i] - B[i]), B[i]};

    st = pair(st.first + st.second, st.first - st.second);
    et = pair(et.first + et.second, et.first - et.second);

    lines.push_back({st.first, st.second, et.first, et.second, C[i]});
    assert(st < et && (st.first == et.first || st.second == et.second));

    coords.emplace_back(st.first);
    coords.emplace_back(st.second);
    coords.emplace_back(et.first);
    coords.emplace_back(et.second);
  }

  for (int i = 0; i < Q; i++) {
    pair<lint, lint> st = {P[i], X[i]};
    st = pair(st.first + st.second, st.first - st.second);
    query.push_back({st.first, st.second, i});
  }

  sort(begin(coords), end(coords));
  coords.resize(unique(begin(coords), end(coords)) - begin(coords));
  const auto Coord = [&](lint x) {
    return lower_bound(begin(coords), end(coords), x) - begin(coords);
  };

  for (auto &l : lines) {
    for (int i = 0; i < 4; i++) {
      l[i] = Coord(l[i]);
    }
  }

  for (int rep = 0; rep < 2; rep++) {
    sort(begin(lines), end(lines));

    int query_ptr = 0;
    sort(begin(query), end(query));
    reverse(begin(query), end(query));

    vector<lint> dp(coords.size());
    for (int x = int(coords.size()) - 1; x >= 1; x--) {
      vector<lint> cost_horz(coords.size());
      vector<lint> cost_vert(coords.size());

      vector<lint> last = dp;
      for (int lid = 0; lid < int(lines.size()); lid++) {
        auto l = lines[lid];
        if (l[0] == l[2] && l[0] == x) { // horizontal line
          for (int y = l[1]; y < l[3]; y++) {
            cost_horz[y] = max(cost_horz[y], l[4]);
          }
        }
        if (l[1] == l[3] && l[0] <= x && x < l[2]) { // vertical line
          dp[l[1]] = max(dp[l[1]], last[l[1]] + (coords[x + 1] - coords[x]) * l[4]);
        }
        if (l[1] == l[3] && l[0] < x && x <= l[2]) {
          cost_vert[l[1]] = max(cost_vert[l[1]], l[4]);
        }
      }

      for (int y = int(coords.size()) - 2; y >= 0; y--) {
        dp[y] = max(dp[y], cost_horz[y] * (coords[y + 1] - coords[y]) + dp[y + 1]);
      }

      // Convex Hull Trick
      vector<pair<lint, lint>> hull;

      const auto Check = [&](pair<lint, lint> a, pair<lint, lint> b, pair<lint, lint> c) -> bool {
        return double(b.second - a.second) / double(a.first - b.first) <
               double(c.second - b.second) / double(b.first - c.first);
      };

      const auto Insert = [&](lint a, lint b) -> void {
        while (!hull.empty() && hull.back().first <= a) {
          assert(hull.back().second <= b);
          hull.pop_back(); // all line (a, b) and query (x) are non-negative integers
        }
        // while (hull.size() > 1 && !Check({a, b}, hull.back(), end(hull)[-2])) {
        //   hull.pop_back();
        // }
        hull.emplace_back(a, b);
      };

      const auto Query = [&](lint x) -> lint {
        lint res = 0;
        for (auto h : hull) res = max(res, h.first * x + h.second);
        return res;
        int lo = 0, hi = int(hull.size()) - 1;
        while (lo < hi) {
          int md = (lo + hi) / 2;
          if (hull[md].first * x + hull[md].second > hull[md + 1].first * x + hull[md + 1].second) {
            hi = md;
          } else {
            lo = md + 1;
          }
        }
        return hull[lo].first * x + hull[lo].second;
      };

      vector<array<lint, 4>> query_list;

      while (query_ptr < int(query.size()) && coords[x - 1] < query[query_ptr][0]) {
        auto q = query[query_ptr++];
        int yinit = lower_bound(begin(coords), end(coords), q[1]) - begin(coords);
        if (coords[x] == q[0]) {
          ans[q[2]] = max(ans[q[2]], dp[yinit] + (coords[yinit] - q[1]) * cost_horz[yinit - 1]);
        } else {
          query_list.push_back({yinit, q[0], q[1], q[2]});
        }
      }

      int inserted_y = int(coords.size());
      sort(begin(query_list), end(query_list));
      reverse(begin(query_list), end(query_list));

      for (auto q : query_list) {
        int yinit = q[0];

        // for (int y = yinit; y < int(coords.size()); y++) {
        //   ans[q[3]] = max(ans[q[3]], dp[y] + (coords[x] - q[1]) * cost_vert[y]);
        // }

        // Note that dp[y] >= dp[y + 1]
        // Thus, while slope[y] >= CHT.back().slope, pop CHT.back(). Afterwards, the slope is
        // still sorted when we add line y. This works since for all input f(x), x >= 0 holds,
        // thus a greater slope is always optimal if the dp[y] is also greater.
        // This allows us to do CHT insert in O(1).

        while (yinit < inserted_y) {
          Insert(cost_vert[inserted_y - 1], dp[inserted_y - 1]);
          inserted_y -= 1;
        }

        ans[q[3]] = max(ans[q[3]], Query(coords[x] - q[1]));
      }
    }

    for (int i = 0; i < N; i++) {
      swap(lines[i][0], lines[i][1]);
      swap(lines[i][2], lines[i][3]);
    }
    for (int i = 0; i < Q; i++) {
      swap(query[i][0], query[i][1]);
    }
  }

  for (int i = 0; i < Q; i++) {
    assert(ans[i] % 4 == 0);
    cout << (ans[i] / 4) << '\n';
  }
  return 0;
}

Compilation message

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:118:18: warning: variable 'Check' set but not used [-Wunused-but-set-variable]
  118 |       const auto Check = [&](pair<lint, lint> a, pair<lint, lint> b, pair<lint, lint> c) -> bool {
      |                  ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3766 ms 184380 KB Output is correct
2 Correct 3746 ms 184604 KB Output is correct
3 Correct 3509 ms 305760 KB Output is correct
4 Correct 3681 ms 240124 KB Output is correct
5 Correct 4166 ms 305876 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1171 ms 1112 KB Output is correct
2 Correct 1152 ms 1024 KB Output is correct
3 Correct 1153 ms 992 KB Output is correct
4 Correct 139 ms 844 KB Output is correct
5 Correct 715 ms 844 KB Output is correct
6 Correct 807 ms 844 KB Output is correct
7 Correct 1111 ms 1072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1171 ms 1112 KB Output is correct
2 Correct 1152 ms 1024 KB Output is correct
3 Correct 1153 ms 992 KB Output is correct
4 Correct 139 ms 844 KB Output is correct
5 Correct 715 ms 844 KB Output is correct
6 Correct 807 ms 844 KB Output is correct
7 Correct 1111 ms 1072 KB Output is correct
8 Correct 1604 ms 1228 KB Output is correct
9 Correct 1686 ms 3840 KB Output is correct
10 Correct 1533 ms 1416 KB Output is correct
11 Correct 136 ms 1168 KB Output is correct
12 Correct 998 ms 1380 KB Output is correct
13 Correct 1208 ms 1192 KB Output is correct
14 Correct 948 ms 1264 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1171 ms 1112 KB Output is correct
2 Correct 1152 ms 1024 KB Output is correct
3 Correct 1153 ms 992 KB Output is correct
4 Correct 139 ms 844 KB Output is correct
5 Correct 715 ms 844 KB Output is correct
6 Correct 807 ms 844 KB Output is correct
7 Correct 1111 ms 1072 KB Output is correct
8 Correct 1604 ms 1228 KB Output is correct
9 Correct 1686 ms 3840 KB Output is correct
10 Correct 1533 ms 1416 KB Output is correct
11 Correct 136 ms 1168 KB Output is correct
12 Correct 998 ms 1380 KB Output is correct
13 Correct 1208 ms 1192 KB Output is correct
14 Correct 948 ms 1264 KB Output is correct
15 Correct 1369 ms 4484 KB Output is correct
16 Correct 1396 ms 4472 KB Output is correct
17 Correct 1223 ms 5624 KB Output is correct
18 Correct 183 ms 5240 KB Output is correct
19 Correct 846 ms 6448 KB Output is correct
20 Correct 936 ms 3972 KB Output is correct
21 Correct 759 ms 6544 KB Output is correct

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3766 ms 184380 KB Output is correct
2 Correct 3746 ms 184604 KB Output is correct
3 Correct 3509 ms 305760 KB Output is correct
4 Correct 3681 ms 240124 KB Output is correct
5 Correct 4166 ms 305876 KB Output is correct
6 Correct 1171 ms 1112 KB Output is correct
7 Correct 1152 ms 1024 KB Output is correct
8 Correct 1153 ms 992 KB Output is correct
9 Correct 139 ms 844 KB Output is correct
10 Correct 715 ms 844 KB Output is correct
11 Correct 807 ms 844 KB Output is correct
12 Correct 1111 ms 1072 KB Output is correct
13 Correct 1604 ms 1228 KB Output is correct
14 Correct 1686 ms 3840 KB Output is correct
15 Correct 1533 ms 1416 KB Output is correct
16 Correct 136 ms 1168 KB Output is correct
17 Correct 998 ms 1380 KB Output is correct
18 Correct 1208 ms 1192 KB Output is correct
19 Correct 948 ms 1264 KB Output is correct
20 Correct 1369 ms 4484 KB Output is correct
21 Correct 1396 ms 4472 KB Output is correct
22 Correct 1223 ms 5624 KB Output is correct
23 Correct 183 ms 5240 KB Output is correct
24 Correct 846 ms 6448 KB Output is correct
25 Correct 936 ms 3972 KB Output is correct
26 Correct 759 ms 6544 KB Output is correct
27 Correct 5465 ms 260280 KB Output is correct
28 Correct 5479 ms 260068 KB Output is correct
29 Correct 5073 ms 363980 KB Output is correct
30 Correct 4675 ms 363868 KB Output is correct
31 Correct 5923 ms 221012 KB Output is correct
32 Correct 9037 ms 229892 KB Output is correct
33 Correct 3506 ms 343544 KB Output is correct