oj.uz

Submission #388954

# Submission time Handle Problem Language Result Execution time Memory
388954 2021-04-13T11:23:09 Z rama_pang Bodyguard (JOI21_bodyguard) C++17
100 / 100
 6103 ms 306456 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 Floor = [&](lint x, lint y) -> lint {
        if (y < 0) x *= -1, y *= -1;
        return x / y - (x < 0 && x % y);
      };

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

      const auto Insert = [&](lint a, lint b) -> void {
        while (!hull.empty() && hull.back().first <= a) {
          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 {
        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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3792 ms 184368 KB Output is correct
2 Correct 3768 ms 184600 KB Output is correct
3 Correct 3454 ms 305792 KB Output is correct
4 Correct 3473 ms 240124 KB Output is correct
5 Correct 4358 ms 305808 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 1148 KB Output is correct
2 Correct 1302 ms 1032 KB Output is correct
3 Correct 1271 ms 940 KB Output is correct
4 Correct 151 ms 844 KB Output is correct
5 Correct 826 ms 852 KB Output is correct
6 Correct 930 ms 844 KB Output is correct
7 Correct 1257 ms 1116 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 1148 KB Output is correct
2 Correct 1302 ms 1032 KB Output is correct
3 Correct 1271 ms 940 KB Output is correct
4 Correct 151 ms 844 KB Output is correct
5 Correct 826 ms 852 KB Output is correct
6 Correct 930 ms 844 KB Output is correct
7 Correct 1257 ms 1116 KB Output is correct
8 Correct 1928 ms 1420 KB Output is correct
9 Correct 1940 ms 1332 KB Output is correct
10 Correct 1678 ms 1388 KB Output is correct
11 Correct 149 ms 1168 KB Output is correct
12 Correct 1126 ms 1220 KB Output is correct
13 Correct 1343 ms 1256 KB Output is correct
14 Correct 1058 ms 1448 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 1148 KB Output is correct
2 Correct 1302 ms 1032 KB Output is correct
3 Correct 1271 ms 940 KB Output is correct
4 Correct 151 ms 844 KB Output is correct
5 Correct 826 ms 852 KB Output is correct
6 Correct 930 ms 844 KB Output is correct
7 Correct 1257 ms 1116 KB Output is correct
8 Correct 1928 ms 1420 KB Output is correct
9 Correct 1940 ms 1332 KB Output is correct
10 Correct 1678 ms 1388 KB Output is correct
11 Correct 149 ms 1168 KB Output is correct
12 Correct 1126 ms 1220 KB Output is correct
13 Correct 1343 ms 1256 KB Output is correct
14 Correct 1058 ms 1448 KB Output is correct
15 Correct 2017 ms 4088 KB Output is correct
16 Correct 2086 ms 4092 KB Output is correct
17 Correct 1549 ms 5236 KB Output is correct
18 Correct 182 ms 4992 KB Output is correct
19 Correct 917 ms 6264 KB Output is correct
20 Correct 1039 ms 3844 KB Output is correct
21 Correct 854 ms 6500 KB Output is correct

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3792 ms 184368 KB Output is correct
2 Correct 3768 ms 184600 KB Output is correct
3 Correct 3454 ms 305792 KB Output is correct
4 Correct 3473 ms 240124 KB Output is correct
5 Correct 4358 ms 305808 KB Output is correct
6 Correct 1294 ms 1148 KB Output is correct
7 Correct 1302 ms 1032 KB Output is correct
8 Correct 1271 ms 940 KB Output is correct
9 Correct 151 ms 844 KB Output is correct
10 Correct 826 ms 852 KB Output is correct
11 Correct 930 ms 844 KB Output is correct
12 Correct 1257 ms 1116 KB Output is correct
13 Correct 1928 ms 1420 KB Output is correct
14 Correct 1940 ms 1332 KB Output is correct
15 Correct 1678 ms 1388 KB Output is correct
16 Correct 149 ms 1168 KB Output is correct
17 Correct 1126 ms 1220 KB Output is correct
18 Correct 1343 ms 1256 KB Output is correct
19 Correct 1058 ms 1448 KB Output is correct
20 Correct 2017 ms 4088 KB Output is correct
21 Correct 2086 ms 4092 KB Output is correct
22 Correct 1549 ms 5236 KB Output is correct
23 Correct 182 ms 4992 KB Output is correct
24 Correct 917 ms 6264 KB Output is correct
25 Correct 1039 ms 3844 KB Output is correct
26 Correct 854 ms 6500 KB Output is correct
27 Correct 6103 ms 202396 KB Output is correct
28 Correct 6103 ms 202404 KB Output is correct
29 Correct 5839 ms 306360 KB Output is correct
30 Correct 3641 ms 306032 KB Output is correct
31 Correct 2747 ms 191528 KB Output is correct
32 Correct 4244 ms 189260 KB Output is correct
33 Correct 3548 ms 306456 KB Output is correct