oj.uz

Submission #388932

# Submission time Handle Problem Language Result Execution time Memory
388932 2021-04-13T10:19:37 Z rama_pang Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 211288 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 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.0

# Verdict Execution time Memory Grader output
1 Correct 12119 ms 211200 KB Output is correct
2 Correct 11925 ms 211288 KB Output is correct
3 Correct 8154 ms 200292 KB Output is correct
4 Correct 8117 ms 197044 KB Output is correct
5 Execution timed out 25020 ms 195464 KB Time limit exceeded

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 1124 KB Output is correct
2 Correct 1338 ms 1092 KB Output is correct
3 Correct 1325 ms 1132 KB Output is correct
4 Correct 152 ms 844 KB Output is correct
5 Correct 824 ms 844 KB Output is correct
6 Correct 960 ms 844 KB Output is correct
7 Correct 1280 ms 1180 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 1124 KB Output is correct
2 Correct 1338 ms 1092 KB Output is correct
3 Correct 1325 ms 1132 KB Output is correct
4 Correct 152 ms 844 KB Output is correct
5 Correct 824 ms 844 KB Output is correct
6 Correct 960 ms 844 KB Output is correct
7 Correct 1280 ms 1180 KB Output is correct
8 Correct 1812 ms 1264 KB Output is correct
9 Correct 1770 ms 1324 KB Output is correct
10 Correct 1717 ms 1512 KB Output is correct
11 Correct 161 ms 912 KB Output is correct
12 Correct 1112 ms 1440 KB Output is correct
13 Correct 1354 ms 1160 KB Output is correct
14 Correct 1111 ms 1188 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 1124 KB Output is correct
2 Correct 1338 ms 1092 KB Output is correct
3 Correct 1325 ms 1132 KB Output is correct
4 Correct 152 ms 844 KB Output is correct
5 Correct 824 ms 844 KB Output is correct
6 Correct 960 ms 844 KB Output is correct
7 Correct 1280 ms 1180 KB Output is correct
8 Correct 1812 ms 1264 KB Output is correct
9 Correct 1770 ms 1324 KB Output is correct
10 Correct 1717 ms 1512 KB Output is correct
11 Correct 161 ms 912 KB Output is correct
12 Correct 1112 ms 1440 KB Output is correct
13 Correct 1354 ms 1160 KB Output is correct
14 Correct 1111 ms 1188 KB Output is correct
15 Correct 1826 ms 4484 KB Output is correct
16 Correct 1827 ms 4472 KB Output is correct
17 Correct 1577 ms 4228 KB Output is correct
18 Correct 248 ms 4220 KB Output is correct
19 Correct 1289 ms 3972 KB Output is correct
20 Correct 1527 ms 3972 KB Output is correct
21 Correct 1610 ms 3788 KB Output is correct

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 12119 ms 211200 KB Output is correct
2 Correct 11925 ms 211288 KB Output is correct
3 Correct 8154 ms 200292 KB Output is correct
4 Correct 8117 ms 197044 KB Output is correct
5 Execution timed out 25020 ms 195464 KB Time limit exceeded