Submission #1206045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206045		mychecksedad	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	4 / 100	5076 ms	29972 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 2e6+10, K = 52, MX = 30;

int n;
int a[N], b[N], c[N], T[M], lazy[M], T2[M], lazy2[M];
array<int, 2> to[N];

array<int, 2> gett(int val, int k){
  return array<int,2>{(lower_bound(b+1, b+1+n, val - k) - b), (upper_bound(b+1, b+1+n, val + k) - b - 1)};
}
void push(int k){
  T[k<<1] += lazy[k];
  T[k<<1|1] += lazy[k];
  lazy[k<<1|1] += lazy[k];
  lazy[k<<1] += lazy[k];
  lazy[k] = 0;

  T2[k<<1] += lazy2[k];
  T2[k<<1|1] += lazy2[k];
  lazy2[k<<1|1] += lazy2[k];
  lazy2[k<<1] += lazy2[k];
  lazy2[k] = 0;
}

void build(int l, int r, int k){
  lazy[k] = 0;
  lazy2[k] = 0;
  if(l == r){
    T[k] = -l;
    T2[k] = 0;
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  T[k] = min(T[k<<1], T[k<<1|1]);
  T2[k] = min(T2[k<<1], T2[k<<1|1]);
}
void upd(int l, int r, int ql, int qr, int k, int val){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    T[k] += val;
    lazy[k] += val;
    return;
  }
  push(k);
  int mid = l+r>>1;
  upd(l, mid, ql, qr, k<<1, val);
  upd(mid+1, r, ql, qr, k<<1|1, val);
  T[k] = min(T[k<<1], T[k<<1|1]);
}

void upd2(int l, int r, int ql, int qr, int k, int val){
  if(ql > r || l > qr) return;
  if(ql <= l && r <= qr){
    T2[k] += val;
    lazy2[k] += val;
    return;
  }
  push(k);
  int mid = l+r>>1;
  upd2(l, mid, ql, qr, k<<1, val);
  upd2(mid+1, r, ql, qr, k<<1|1, val);
  T2[k] = min(T2[k<<1], T2[k<<1|1]);
}

bool f(int k){
  vector<bool> B(2*n+3);
  vector<bool> C(2*n+3);

  for(int rep = 0; rep < 2; ++rep){

    for(int i = 1; i <= n*3; ++i){
      to[i] = gett(a[i], k);
      // cerr << k << ' '<< a[i] << ' ' << to[i][0] << ' ' << to[i][1] << '\n';
    }
    // en;
    int cnt_bad = 0;
    build(1, n, 1);
    for(int i = 1; i <= n; ++i){
      upd(1, n, to[i][0], n, 1, 1);
      upd2(1, n, to[i][0], to[i][1], 1, 1);
      if(to[i][0] > to[i][1]) cnt_bad++;
    }

    for(int i = n + 1; i <= 3 * n + 1; ++i){
      if(T[1] >= 0 && T2[1] > 0 && cnt_bad == 0){ // i-n ... i-1 is nice
        B[i - n] = 1;
      }
      if(i > 3*n) break;

      if(to[i - n][0] > to[i - n][1]) cnt_bad--;

      upd(1, n, to[i - n][0], n, 1, -1);
      upd2(1, n, to[i - n][0], to[i - n][1], 1, -1);
      
      if(to[i][0] > to[i][1]) cnt_bad++;

      upd(1, n, to[i][0], n, 1, 1);
      upd2(1, n, to[i][0], to[i][1], 1, 1);
    }

    for(int i = 1; i <= n; ++i){
      swap(b[i], c[i]);
    }
    B.swap(C);
  }

  // for(int i = 1; i <= n*2; ++i){
  //   cerr << B[i];
  // }
  // en;
  // for(int i = 1; i <= n*2; ++i){
  //   cerr << C[i];
  // }
  // en;

  for(int i = 1; i <= n; ++i){
    if(B[i] && C[i + n]) return 1;
    if(C[i] && B[i + n]) return 1;
  }
  return 0;
}

void solve(){
  cin >> n;
  for(int i = 1; i <= n*2; ++i){
    cin >> a[i];
  }
  for(int i = n+n+1; i <= n+n+n; ++i) a[i] = a[i-n-n];
  for(int i = 1; i <= n; ++i){
    cin >> b[i];
  }
  for(int i = 1; i <= n; ++i){
    cin >> c[i];
  }
  sort(b+1, b+1+n);
  sort(c+1, c+1+n);
  int L = 0, R = 1e9, ans = 1e9;
  while(L <= R){
    int mid = L+R>>1;
    if(f(mid)){
      ans = mid;
      R = mid-1;
    }else L = mid+1;
  }
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

Main.cpp: In function 'std::array<int, 2> gett(int, int)':
Main.cpp:21:57: warning: narrowing conversion of '((std::lower_bound<int*, int>((((int*)(& b)) + 4), (((int*)(& b)) + ((((sizetype)n) + 1) * 4)), (val - k)) - ((int*)(& b))) <unknown operator> 4)' from 'long int' to 'int' [-Wnarrowing]
   21 |   return array<int,2>{(lower_bound(b+1, b+1+n, val - k) - b), (upper_bound(b+1, b+1+n, val + k) - b - 1)};
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
Main.cpp:21:101: warning: narrowing conversion of '(((std::upper_bound<int*, int>((((int*)(& b)) + 4), (((int*)(& b)) + ((((sizetype)n) + 1) * 4)), (val + k)) - ((int*)(& b))) <unknown operator> 4) - 1)' from 'long int' to 'int' [-Wnarrowing]
   21 |   return array<int,2>{(lower_bound(b+1, b+1+n, val - k) - b), (upper_bound(b+1, b+1+n, val + k) - b - 1)};
      |                                                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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