Submission #388932

#	Time	Username	Problem	Language	Result	Execution time	Memory
388932		rama_pang	Bodyguard (JOI21_bodyguard)	C++17	42 / 100	25020 ms	211288 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 rightwars (downwards is
  // symnetric). Then there are O(N) distinct y coordinates
  // we can start on, so this runs in O(Q 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));
    sort(begin(query), end(query));
    reverse(begin(query), end(query));

    int query_ptr = 0;

    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 (auto l : lines) {
        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]);
      }

      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 {
          for (int y = yinit; y < int(coords.size()); y++) {
            ans[q[2]] = max(ans[q[2]], dp[y] + (coords[x] - q[0]) * cost_vert[y]);
          }
        }
      }
    }

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