Submission #1211630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211630		abczz	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	0 / 100	1684 ms	33776 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

ll cnt[600000];
ll n, A[600000], B[300000], C[300000];
ll minrnk[600000], maxrnk[600000], G[600000];

vector<ll> solve(ll d) {
  if (B[0] < A[0]-d || A[0]+d < B[0]) return {};
  vector <ll> ret;
  int j = 0, k = 0;
  vector <ll> X, Y;
  for (int i=0; i<n; ++i) {
    G[i] = -1;
    while (j < n && B[j] < A[i]-d) ++j;
    while (k+1 < n && B[k+1] <= A[i]+d) ++k;
    minrnk[i] = j-i, maxrnk[i] = k-i;
    if (minrnk[i] > 0 && (X.empty() || minrnk[X.back()] < minrnk[i])) X.push_back(i);
    if (Y.empty() || maxrnk[Y.back()] >= maxrnk[i]) Y.push_back(i);
  }
  reverse(X.begin(), X.end());
  j = 0;
  ll s = 0; 
  G[0] = 0;
  for (int i=n-1; i>=0; --i) {
    if (X.empty() && (Y.empty() || maxrnk[Y.back()] >= s)) ret.push_back(i);
    if (i) {
      ++s;
      while (A[2*n-s] >= A[j] && j <= n-1) {
        ++j;
        G[j] = G[j-1];
      }
      ++G[j];
      while (!X.empty() && (X.back() >= i || (j <= X.back() && minrnk[X.back()] <= s))) X.pop_back();
      while (!Y.empty() && (Y.back() >= i || (Y.back() < j && maxrnk[Y.back()] >= G[Y.back()]))) Y.pop_back();
    }
  }
  return ret;
}
void swp() {
  for (int i=1; i<n; ++i) swap(A[i], A[2*n-i]);
}
void swp2() {
  for (int i=0; i<n; ++i) swap(B[i], C[i]);
  for (int i=1; i<n/2; ++i) swap(A[i], A[n-i]);
  for (int i=n+1; i<3*n/2; ++i) swap(A[i], A[3*n-i]);
  swap(A[0], A[n]);
  for (int i=0; i<2*n; ++i) A[i] = 1e9-A[i];
  for (int i=0; i<n; ++i) B[i] = 1e9-B[i], C[i] = 1e9-C[i];
  reverse(B, B+n);
  reverse(C, C+n);
}
bool solve2(ll mid) {
  for (int i=0; i<n; ++i) cnt[i] = 0;
  auto u = solve(mid);
  for (auto x : u) ++cnt[x];
  swp();
  auto v = solve(mid);
  for (auto x : v) ++cnt[n-1-x];
  swp2();
  auto g = solve(mid);
  for (auto x : g) ++cnt[x];
  swp();
  auto h = solve(mid);
  for (auto x : h) ++cnt[n-1-x];
  swp2();
  for (int i=0; i<n; ++i) if (cnt[i] == 4) return 1;
  return 0;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i=0; i<2*n; ++i) cin >> A[i];
  for (int i=0; i<n; ++i) cin >> B[i];
  for (int i=0; i<n; ++i) cin >> C[i];
  sort(B, B+n);
  sort(C, C+n);
  ll l = 0, r = 1e9, mid;
  while (l < r) {
    mid = (l+r)/2;
    for (int i=0; i<n; ++i) cnt[i] = 0;
    bool ok = 0;
    if (!solve2(mid)) {
      for (int i=0; i<n; ++i) swap(B[i], C[i]);
      if (solve2(mid)) ok = 1;
      for (int i=0; i<n; ++i) swap(B[i], C[i]);
    }
    else ok = 1;
    if (ok) r = mid;
    else l = mid+1;
  }
  cout << l << '\n';
}

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