Submission #1211765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211765		abczz	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	1935 ms	46888 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#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], Z[600000];

vector<ll> solve(ll d, ll w) {
  if (B[0] < A[0]-d || A[0]+d < B[0]) return {};
  vector <ll> ret;
  int j = 0, k = 0;
  ll z = 1e9;
  vector <ll> X;
  for (int i=0; i<n; ++i) {
    G[i] = Z[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 (j > k) z = min(z, (ll)i);
    if (minrnk[i] > 0 && (X.empty() || minrnk[X.back()] < minrnk[i])) X.push_back(i);
  }
  reverse(X.begin(), X.end());
  j = 0;
  ll s = 0;
  vector <array<ll, 2>> R;
  for (int i=n-1; i>=0; --i) {
    if (j <= i) R.push_back({j, i});
    if (i) {
      ++s;
      while ((w == 0 ? A[2*n-s] >= A[j] : A[2*n-s] > A[j]) && j <= n-1) ++j;
    }
  }
  ll f = 1e18;
  for (int i=R.size()-1; i>=0; --i) {
    if (i == R.size()-1) {
      for (int j=R[i][0]; j<=R[i][1]; ++j) f = min(f, maxrnk[j]);
    }
    else {
      for (int j=R[i][0]; j<R[i+1][0]; ++j) f = min(f, maxrnk[j]);
      for (int j=R[i+1][1]+1; j<=R[i][1]; ++j) f = min(f, maxrnk[j]);
    }
    Z[R[i][1]] = f;
  }
  j = s = 0;
  G[0] = 0;
  if (maxrnk[0] < 0) z = 0;
  for (int i=n-1; i>=0; --i) {
    if (X.empty() && (j <= i ? Z[i] >= s : 1) && i < z) ret.push_back(i);
    if (i) {
      ++s;
      while ((w == 0 ? A[2*n-s] >= A[j] : A[2*n-s] > A[j]) && j <= n-1) {
        ++j;
        G[j] = G[j-1];
        if (maxrnk[j] < G[j]) z = min(z, (ll)j);
      }
      ++G[j];
      if (maxrnk[j] < G[j]) z = min(z, (ll)j);
      while (!X.empty() && (X.back() >= i || (j <= X.back() && minrnk[X.back()] <= s))) X.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, 0);
  for (auto x : u) ++cnt[x];
  swp();
  auto v = solve(mid, 1);
  for (auto x : v) ++cnt[n-1-x];
  swp2();
  auto g = solve(mid, 0);
  for (auto x : g) ++cnt[x];
  swp();
  auto h = solve(mid, 1);
  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 >> 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: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 37 / 37
• Subtask 5: 33 / 33