Submission #1241798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241798		hengliao	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	2727 ms	32548 KiB

Main

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

const ll mxN=2e6+5;
const ll inf=1e18;

ll n;

ll a[mxN];
vll b, c;
bool pos[mxN][2];

void solve(){
	cin>>n;
	for(ll i=0;i<2*n;i++){
		cin>>a[i];
		a[i+2*n]=a[i];
	}
	b=vll(n);
	for(auto &it:b){
		cin>>it;
	}
	c=vll(n);
	for(auto &it:c){
		cin>>it;
	}
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());

	auto qry=[&](ll tar, ll diff, ll flag){
		if(flag==0){
			ll mx=tar+diff;
			ll lef=0, rig=n-1;
			ll good1=-1;
			while(lef<=rig){
				ll mid=(lef+rig)/2;
				if(b[mid]<=mx){
					good1=mid;
					lef=mid+1;
				}
				else{
					rig=mid-1;
				}
			}
			// if(good1!=-1 && b[good1]<tar){
			// 	good1=-1;
			// }
			ll mn=tar-diff;
			lef=0;
			rig=n-1;
			ll good2=n;
			while(lef<=rig){
				ll mid=(lef+rig)/2;
				if(b[mid]>=mn){
					good2=mid;
					rig=mid-1;
				}
				else{
					lef=mid+1;
				}
			}
			// if(good2!=n && b[good2]>tar){
			// 	good2=n;
			// }
			if(good2>good1){
				return make_pair(n, -1LL);
			}
			return make_pair(good2, good1);
		}
		else{
			ll mx=tar+diff;
			ll lef=0, rig=n-1;
			ll good1=-1;
			while(lef<=rig){
				ll mid=(lef+rig)/2;
				if(c[mid]<=mx){
					good1=mid;
					lef=mid+1;
				}
				else{
					rig=mid-1;
				}
			}
			// if(good1!=-1 && c[good1]<tar){
			// 	good1=-1;
			// }
			ll mn=tar-diff;
			lef=0;
			rig=n-1;
			ll good2=n;
			while(lef<=rig){
				ll mid=(lef+rig)/2;
				if(c[mid]>=mn){
					good2=mid;
					rig=mid-1;
				}
				else{
					lef=mid+1;
				}
			}
			// if(good2!=n && c[good2]>tar){
			// 	good2=n;
			// }
			if(good2>good1){
				return make_pair(n, -1LL);
			}
			return make_pair(good2, good1);
		}
	};

	vll v(2*n);

	ll pt=2*n;

	for(ll i=0;i<n;i++){
		while(pt-1>=n && a[pt-1]<a[i]){
			pt--;
		}
		v[i]=pt;
	}

	pt=-1;

	for(ll i=2*n-1;i>=n;i--){
		while(pt+1<n && a[pt+1]<=a[i]){
			pt++;
		}
		v[i]=pt;
	}

	auto dumb=[&](ll idx){
		return v[idx];
	};

	vll bad_cnt(2*n);

	auto mark=[&](ll lef, ll rig){
		// cout<<"marking "<<lef<<' '<<rig<<'\n';
		if(lef<=rig){
			bad_cnt[lef]++;
			if(rig<2*n-1) bad_cnt[rig+1]--;
		}
		else{
			bad_cnt[lef]++;
			bad_cnt[0]++;
			if(rig<2*n-1) bad_cnt[rig+1]--;
		}
	};

	auto dis=[&](ll f, ll s){
		if(f<s){
			return s-f;
		}
		else{
			return s+2*n-f;
		}
	};

	auto end_to_start=[&](ll tar){
		ll re=tar-n+1+2*n;
		re%=2*n;
		return re;
	};

	auto check=[&](ll diff){
		memset(pos, 0, sizeof(pos));
		for(ll rep=0;rep<2;rep++){
			// cout<<"rep: "<<rep<<'\n';
			bad_cnt=vll(2*n, 0);
			for(ll i=0;i<n;i++){
				// cout<<"considering "<<i<<'\n';
				pll p=qry(a[i], diff, rep);
				// cout<<"range: "<<p.F<<' '<<p.S<<'\n';
				if(p.F==n){
					mark((i-n+1+2*n)%(2*n), i);
				}
				else{
					ll tep=dumb(i);
					if(tep==2*n){
						if(p.F>i){
							mark((i-n+1+2*n)%(2*n), i);
						}
						else{
							if(p.S<i){
								if(i-p.S-1>=i-n+1) mark((i-n+1+2*n)%(2*n), (i-p.S-1+2*n)%(2*n));
							}
							if(p.F>0){
								if(i-p.F+1>=i-n+1) mark(((i-p.F+1+2*n)%(2*n)), i);
								else mark((i-n+1+2*n)%(2*n), i);
							}
						}
						continue;
					}
					ll d=dis(tep, i);
					if(d<p.F){
						mark((i-n+1+2*n)%(2*n), i);
					}
					else{
						if(p.F>0){
							if(tep<=i+n-1 && i+n-tep>=p.F){

							}
							else{
								// cout<<"hi2\n";
								if(i-p.F+1>=i-n+1) mark(((i-p.F+1+2*n)%(2*n)), i);
								else mark((i-n+1+2*n)%(2*n), i);
							}
						}
						if(p.S<d){
							ll bk=tep-n+1;
							if(bk<=i && i-bk+1>p.S){
								mark((i-n+1+2*n)%(2*n), i);
							}
							else{
								// cout<<"hi\n";
								if(i-p.S-1>=i-n+1) mark((i-n+1+2*n)%(2*n), (i-p.S-1+2*n)%(2*n));
							}
						}
					}
				}
			}
			for(ll i=n;i<2*n;i++){
				// cout<<"considering "<<i<<'\n';
				pll p=qry(a[i], diff, rep);
				// cout<<"range: "<<p.F<<' '<<p.S<<'\n';
				if(p.F==n){
					mark((i-n+1+2*n)%(2*n), i);
				}
				else{
					ll tep=dumb(i);
					if(tep==-1){
						if(p.F>2*n-1-i){
							mark((i-n+1+2*n)%(2*n), i);
						}
						else{
							if(p.F>0){
								mark(end_to_start(i), end_to_start((i+p.F-1)%(2*n)));
							}
							if(p.S<2*n-1-i){
								mark(end_to_start((i+p.S+1)%(2*n)), i);
							}
						}
						continue;
					}
					ll d=dis(i, tep);
					// cout<<"d: "<<d<<'\n';
					if(d<p.F){
						mark((i-n+1+2*n)%(2*n), i);
					}
					else{
						if(p.F>0){
							ll st=end_to_start(i);
							if(st<=tep && tep-st+1>=p.F){

							}
							else{
								if(i+p.F-1<=i+n-1) mark(end_to_start(i), end_to_start((i+p.F-1)%(2*n)));
								else mark((i-n+1+2*n)%(2*n), i);
							}
							
						}
						if(p.S<d){
							ll st=end_to_start(i);
							if(st<=tep && tep-st+1>p.S){
								mark((i-n+1+2*n)%(2*n), i);
							}
							else{
								// cout<<"hi3\n";
								if(i+p.S+1<=i+n-1) mark(end_to_start((i+p.S+1)%(2*n)), i);
							}
							
						}
					}
				}
			}
			if(bad_cnt[0]==0){
				pos[0][rep]=1;
			}
			for(ll i=1;i<2*n;i++){
				bad_cnt[i]+=bad_cnt[i-1];
				if(bad_cnt[i]==0){
					pos[i][rep]=1;
				}
			}
			// cout<<"_______________\n";
		}
		for(ll i=0;i<n;i++){
			if((pos[i][0] && pos[i+n][1]) || (pos[i][1] && pos[i+n][0])){
				return true;
			}
		}
		return false;
	};

	// bool tep=check(2);

	// cout<<"tep: "<<tep<<'\n';

	ll lef=0, rig=1e9+5;
	ll ans=-1;
	while(lef<=rig){
		ll mid=(lef+rig)/2;
		if(check(mid)){
			ans=mid;
			rig=mid-1;
		}
		else{
			lef=mid+1;
		}
	}

	cout<<ans<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solve();

	return 0;
}

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