Submission #978222

#	Time	Username	Problem	Language	Result	Execution time	Memory
978222		model_code	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	100 / 100	1962 ms	23404 KiB

Main

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

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

  int N;
  cin >> N;
  vector<int> A(2 * N), B(N), C(N);
  for (auto& x : A) cin >> x;
  for (auto& x : B) cin >> x;
  for (auto& x : C) cin >> x;
  sort(begin(B), end(B));
  sort(begin(C), end(C));

  vector<int> A2(A), B2(B), C2(C);
  rotate(begin(A2), begin(A2) + N, end(A2));
  reverse(begin(B2), end(B2));
  reverse(begin(C2), end(C2));
  for (auto& x : A2) x = -x;
  for (auto& x : B2) x = -x;
  for (auto& x : C2) x = -x;

  auto check = [&](int thres) -> bool {
    auto solve_sub = [&](const vector<int>& seedling, const vector<int>& planter) -> vector<bool> {
      vector<int> imos(N + 1);
      {
        int p_l = 0, p_r = 0, s_r = 2 * N;
        for (int i = 0; i < N; ++i) {
          while (p_l < N && planter[p_l] < seedling[i] - thres) p_l += 1;
          while (p_r < N && planter[p_r] <= seedling[i] + thres) p_r += 1;
          while (s_r > N && seedling[s_r - 1] < seedling[i]) s_r -= 1;
          int lowest = i - s_r + N;
          if (p_r <= lowest) continue;
          int l = max(0, i - p_r + 1);
          int r = (p_l <= lowest ? i + 1 : i - p_l + 1);
          if (l < r) {
            imos[l] += 1;
            imos[r] -= 1;
          }
        }
      }
      {
        int p_l = N, p_r = N, s_r = N;
        for (int i = N; i < 2 * N; ++i) {
          while (p_l > 0 && planter[p_l - 1] >= seedling[i] - thres) p_l -= 1;
          while (p_r > 0 && planter[p_r - 1] > seedling[i] + thres) p_r -= 1;
          while (s_r > 0 && seedling[s_r - 1] > seedling[i]) s_r -= 1;
          int lowest = s_r + N - i - 1;
          if (p_r <= lowest) continue;
          int l = (p_l <= lowest ? i - N + 1 : i + p_l - N + 1);
          int r = min(N, i + p_r - N + 1);
          if (l < r) {
            imos[l] += 1;
            imos[r] -= 1;
          }
        }
      }
      vector<bool> ret(N);
      for (int i = 0; i < N; ++i) {
        ret[i] = (imos[i] == N);
        imos[i + 1] += imos[i];
      }
      return ret;
    };
    auto F1 = solve_sub(A, B);
    auto F2 = solve_sub(A2, B2);
    auto G1 = solve_sub(A, C);
    auto G2 = solve_sub(A2, C2);
    for (int i = 0; i < N; ++i) {
      if (F1[i] && G2[i]) return true;
      if (F2[i] && G1[i]) return true;
    }
    return false;
  };

  int ok = 1000000000, ng = -1;
  while (ok - ng > 1) {
    int md = (ok + ng) / 2;
    (check(md) ? ok : ng) = md;
  }
  cout << ok << '\n';
  return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 37 / 37
• Subtask 5: 33 / 33