Submission #388954

#	Time	Username	Problem	Language	Result	Execution time	Memory
388954		rama_pang	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	6103 ms	306456 KiB

bodyguard

#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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 53 / 53