제출 #1194047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194047		avighna	Snowball (JOI21_ho_t2)	C++20	0 / 100	5 ms	328 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), p_max(q);
  int64_t sum = 0, min = inf, max = -inf;
  for (int i = 0; i < q; ++i) {
    sum += wind[i];
    min = std::min(min, sum);
    max = std::max(max, sum);
    p_min[i] = min;
    p_max[i] = max;
  }
  for (int i = 0; i < q; ++i) {
    p_min[i] = -p_min[i];
  }
  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) {
        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) {
        return false;
      }
      return ball[i - 1] + p_max[idx] <= ball[i] - x;
    }) - 1;
    std::cout << max_left + max_right << '\n';
  }
}

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