Submission #386290

#	Time	Username	Problem	Language	Result	Execution time	Memory
386290		model_code	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	6497 ms	1028404 KiB

bodyguard

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