제출 #1194073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194073		avighna	Snowball (JOI21_ho_t2)	C++20	100 / 100	884 ms	8536 KiB

Main

#include <bits/stdc++.h>

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

  const int64_t inf = 1e18;

  int n, q;
  std::cin >> n >> q;
  std::vector<int64_t> ball, wind(q);
  ball.push_back(-inf);
  for (int i = 0; i < n; ++i) {
    int64_t b;
    std::cin >> b;
    ball.push_back(b);
  }
  ball.push_back(inf);
  n += 2;
  for (auto &i : wind) {
    std::cin >> i;
  }

  std::vector<int64_t> p_min(q + 1), p_max(q + 1);
  int64_t sum = 0, min = 0, max = 0;
  for (int i = 0; i < q; ++i) {
    sum += wind[i];
    p_min[i + 1] = -(min = std::min(min, sum));
    p_max[i + 1] = max = std::max(max, sum);
  }
  for (int i = 1; i < n - 1; ++i) {
    int64_t max_right = *std::ranges::partition_point(std::views::iota(int64_t(0), inf), [&](int64_t x) {
      int idx = std::lower_bound(p_max.begin(), p_max.end(), x) - p_max.begin();
      if (idx == q + 1) {
        return false;
      }
      return ball[i] + x <= ball[i + 1] - p_min[idx];
    }) - 1;
    int64_t max_left = *std::ranges::partition_point(std::views::iota(int64_t(0), inf), [&](int64_t x) {
      int idx = std::lower_bound(p_min.begin(), p_min.end(), x) - p_min.begin();
      if (idx == q + 1) {
        return false;
      }
      return ball[i - 1] + p_max[idx] <= ball[i] - x;
    }) - 1;
    std::cout << max_left + max_right << '\n';
  }
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67