oj.uz

Submission #386290

# Submission time Handle Problem Language Result Execution time Memory
386290 2021-04-06T09:49:49 Z model_code Bodyguard (JOI21_bodyguard) C++17
100 / 100
 6497 ms 1028404 KB 
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

using usize = std::size_t;
using i64 = std::int64_t;

static constexpr i64 INF = std::numeric_limits<i64>::max() / 2;

void chmax(i64 &a, const i64 &b) { a = std::max(a, b); }

struct compress {
  std::vector<i64> v;
  compress() {}
  void add(i64 x) { v.push_back(x); }
  void build() {
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
  }

  i64 operator[](usize i) { return v[i]; }
  usize get(i64 x) {
    return std::lower_bound(v.begin(), v.end(), x) - v.begin();
  }
  usize size() { return v.size(); }
};

struct convex_hull_trick {
  struct line {
    i64 a, b;

    i64 eval(i64 x) { return a * x + b; }
  };

  static bool is_necessary(const line &x, const line &y, const line &z) {
    return (x.b - y.b) / (y.a - x.a) < (y.b - z.b) / (z.a - y.a);
  }

  std::vector<line> lines;

  void add(const line &z) {
    while (!lines.empty() && lines.back().a <= z.a) {
      lines.pop_back();
    }
    while (lines.size() >= 2 &&
           !is_necessary(z, lines.back(), *(lines.rbegin() + 1))) {
      lines.pop_back();
    }
    lines.push_back(z);
  }

  i64 get(i64 x) {
    usize l = -1;
    usize r = lines.size();
    while (r - l > 2) {
      const usize ll = (l + l + r) / 3;
      const usize rr = (l + r + r) / 3;
      if (lines[ll].eval(x) < lines[rr].eval(x)) {
        l = ll;
      } else {
        r = rr;
      }
    }
    return lines[(l + r) / 2].eval(x);
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  usize N, Q;
  std::cin >> N >> Q;

  struct vip {
    i64 a, s, t, C;
  };
  std::vector<vip> left, right;
  for (usize i = 0; i != N; i += 1) {
    i64 T, A, B, C;
    std::cin >> T >> A >> B >> C;
    C /= 2;

    if (A < B) {
      right.push_back({T - A, T + A, T + (B - A) + B, C});
    } else {
      left.push_back({T + A, T - A, T + (A - B) - B, C});
    }
  }

  compress cx, cy;
  for (const auto &[a, s, t, C] : left) {
    cx.add(a);
    cy.add(s);
    cy.add(t);
  }
  for (const auto &[a, s, t, C] : right) {
    cy.add(a);
    cx.add(s);
    cx.add(t);
  }
  cx.add(-INF);
  cx.add(INF);
  cx.build();
  cy.add(-INF);
  cy.add(INF);
  cy.build();

  struct plan {
    i64 x, y, ans;
  };
  std::vector<plan> plans(Q);
  for (auto &[x, y, ans] : plans) {
    i64 P, X;
    std::cin >> P >> X;
    x = P + X;
    y = P - X;
    ans = 0;
  }

  std::vector dp(cx.size(), std::vector(cy.size(), i64(0)));
  std::vector dx(cx.size() - 1, std::vector(cy.size() - 1, i64(0)));
  std::vector dy(cx.size() - 1, std::vector(cy.size() - 1, i64(0)));
  for (const auto &[a, s, t, C] : left) {
    const usize x = cx.get(a) - 1;
    for (usize y = cy.get(s); cy[y] != t; y += 1) {
      chmax(dy[x][y], C);
    }
  }
  for (const auto &[a, s, t, C] : right) {
    const usize y = cy.get(a) - 1;
    for (usize x = cx.get(s); cx[x] != t; x += 1) {
      chmax(dx[x][y], C);
    }
  }
  for (usize x = cx.size() - 1; x != 0; x -= 1) {
    for (usize y = cy.size() - 1; y != 0; y -= 1) {
      chmax(dp[x - 1][y], dp[x][y] + dx[x - 1][y - 1] * (cx[x] - cx[x - 1]));
      chmax(dp[x][y - 1], dp[x][y] + dy[x - 1][y - 1] * (cy[y] - cy[y - 1]));
    }
  }

  std::vector p_list(cx.size() - 1,
                     std::vector(cy.size() - 1, std::vector<plan *>()));
  for (auto &p : plans) {
    const auto &[x, y, ans] = p;
    p_list[cx.get(x) - 1][cy.get(y) - 1].push_back(&p);
  }

  for (usize x = cx.size() - 1; x != 0; x -= 1) {
    convex_hull_trick cht;
    for (usize y = cy.size() - 1; y != 0; y -= 1) {
      cht.add({dx[x - 1][y - 1], dp[x][y]});
      for (const auto p : p_list[x - 1][y - 1]) {
        chmax(p->ans, cht.get(cx[x] - p->x));
      }
    }
  }
  for (usize y = cy.size() - 1; y != 0; y -= 1) {
    convex_hull_trick cht;
    for (usize x = cx.size() - 1; x != 0; x -= 1) {
      cht.add({dy[x - 1][y - 1], dp[x][y]});
      for (const auto p : p_list[x - 1][y - 1]) {
        chmax(p->ans, cht.get(cy[y] - p->y));
      }
    }
  }

  for (const auto &[x, y, ans] : plans) {
    std::cout << ans << "\n";
  }

  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4974 ms 584452 KB Output is correct
2 Correct 4918 ms 588376 KB Output is correct
3 Correct 2094 ms 254624 KB Output is correct
4 Correct 1457 ms 129624 KB Output is correct
5 Correct 3106 ms 966420 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2156 ms 830316 KB Output is correct
2 Correct 2156 ms 830212 KB Output is correct
3 Correct 2062 ms 818896 KB Output is correct
4 Correct 4 ms 1132 KB Output is correct
5 Correct 1845 ms 830260 KB Output is correct
6 Correct 1810 ms 830264 KB Output is correct
7 Correct 1787 ms 829164 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2156 ms 830316 KB Output is correct
2 Correct 2156 ms 830212 KB Output is correct
3 Correct 2062 ms 818896 KB Output is correct
4 Correct 4 ms 1132 KB Output is correct
5 Correct 1845 ms 830260 KB Output is correct
6 Correct 1810 ms 830264 KB Output is correct
7 Correct 1787 ms 829164 KB Output is correct
8 Correct 2134 ms 830444 KB Output is correct
9 Correct 2077 ms 830352 KB Output is correct
10 Correct 2081 ms 817392 KB Output is correct
11 Correct 5 ms 1260 KB Output is correct
12 Correct 1844 ms 830352 KB Output is correct
13 Correct 1815 ms 830328 KB Output is correct
14 Correct 1995 ms 830444 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2156 ms 830316 KB Output is correct
2 Correct 2156 ms 830212 KB Output is correct
3 Correct 2062 ms 818896 KB Output is correct
4 Correct 4 ms 1132 KB Output is correct
5 Correct 1845 ms 830260 KB Output is correct
6 Correct 1810 ms 830264 KB Output is correct
7 Correct 1787 ms 829164 KB Output is correct
8 Correct 2134 ms 830444 KB Output is correct
9 Correct 2077 ms 830352 KB Output is correct
10 Correct 2081 ms 817392 KB Output is correct
11 Correct 5 ms 1260 KB Output is correct
12 Correct 1844 ms 830352 KB Output is correct
13 Correct 1815 ms 830328 KB Output is correct
14 Correct 1995 ms 830444 KB Output is correct
15 Correct 2214 ms 833116 KB Output is correct
16 Correct 2268 ms 833020 KB Output is correct
17 Correct 2095 ms 821952 KB Output is correct
18 Correct 19 ms 2924 KB Output is correct
19 Correct 2249 ms 832108 KB Output is correct
20 Correct 1841 ms 832272 KB Output is correct
21 Correct 1967 ms 832196 KB Output is correct

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4974 ms 584452 KB Output is correct
2 Correct 4918 ms 588376 KB Output is correct
3 Correct 2094 ms 254624 KB Output is correct
4 Correct 1457 ms 129624 KB Output is correct
5 Correct 3106 ms 966420 KB Output is correct
6 Correct 2156 ms 830316 KB Output is correct
7 Correct 2156 ms 830212 KB Output is correct
8 Correct 2062 ms 818896 KB Output is correct
9 Correct 4 ms 1132 KB Output is correct
10 Correct 1845 ms 830260 KB Output is correct
11 Correct 1810 ms 830264 KB Output is correct
12 Correct 1787 ms 829164 KB Output is correct
13 Correct 2134 ms 830444 KB Output is correct
14 Correct 2077 ms 830352 KB Output is correct
15 Correct 2081 ms 817392 KB Output is correct
16 Correct 5 ms 1260 KB Output is correct
17 Correct 1844 ms 830352 KB Output is correct
18 Correct 1815 ms 830328 KB Output is correct
19 Correct 1995 ms 830444 KB Output is correct
20 Correct 2214 ms 833116 KB Output is correct
21 Correct 2268 ms 833020 KB Output is correct
22 Correct 2095 ms 821952 KB Output is correct
23 Correct 19 ms 2924 KB Output is correct
24 Correct 2249 ms 832108 KB Output is correct
25 Correct 1841 ms 832272 KB Output is correct
26 Correct 1967 ms 832196 KB Output is correct
27 Correct 6451 ms 1027972 KB Output is correct
28 Correct 6497 ms 1028404 KB Output is correct
29 Correct 4204 ms 972140 KB Output is correct
30 Correct 1249 ms 115840 KB Output is correct
31 Correct 3256 ms 921560 KB Output is correct
32 Correct 4562 ms 986600 KB Output is correct
33 Correct 3082 ms 966584 KB Output is correct