Submission #988482

#	Time	Username	Problem	Language	Result	Execution time	Memory
988482		amirhoseinfar1385	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	30 / 100	5099 ms	86836 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O6,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
const int maxn=300000+10,maxh=maxn*2;
int all[maxn][2],n,inf=1e9,kaf=(1<<20),sz,kk=(1<<19)-1,lnk[maxn][2];
vector<int>allb,allc,alla;
 
struct segment{
	int ps[(1<<21)],sum[(1<<21)];
	void clear(){
		memset(ps,0,sizeof(ps));
		memset(sum,0,sizeof(sum));
	}
	void upd(int i,int w){
		i+=kaf;
		sum[i]+=w;
		i>>=1;
		while(i>0){
			sum[i]+=w;
			ps[i]=min(ps[(i<<1)],sum[(i<<1)]+ps[(i<<1)^1]);
			i>>=1;
		}
		return ;
	}
}segsb,segpb,segsc,segpc;
 
void clear(){
	segsb.clear();
	segpb.clear();
	segsc.clear();
	segpc.clear();
}
 
void fastscan(int &number) { 
    register int c; 
    number = 0; 
    c = getchar(); 
    for (; (c>47 && c<58); c=getchar()) 
        number = number *10 + c - 48; 
} 
 
void vorod(){
	fastscan(n);
	alla.push_back(-1);
	for(int i=0;i<n;i++){
		fastscan(all[i][0]);
		alla.push_back(all[i][0]);
	}
	for(int i=n-1;i>=0;i--){
		fastscan(all[i][1]);
		alla.push_back(all[i][1]);
	}
	sort(alla.begin(),alla.end());
	alla.resize(unique(alla.begin(),alla.end())-alla.begin());
	allb.resize(n);
	allc.resize(n);
	for(int i=0;i<n;i++){
		fastscan(allb[i]);
	}
	for(int i=0;i<n;i++){
		fastscan(allc[i]);
	}
	sort(allb.begin(),allb.end());
	sort(allc.begin(),allc.end());
	for(int i=0;i<n;i++){
		lnk[i][0]=lower_bound(alla.begin(),alla.end(),all[i][0])-alla.begin();
		lnk[i][1]=lower_bound(alla.begin(),alla.end(),all[i][1])-alla.begin();
	}
	sz=alla.size();
}
 
void inssufb(int ind){
	segsb.upd(ind,1);
}
 
void inspsb(int ind){
	segpb.upd(maxh-ind,1);
}
 
void inssufc(int ind){
	segsc.upd(ind,1);
}
 
void inspsc(int ind){
	segpc.upd(maxh-ind,1);
}
 
void insb(int w,int ind){
	int l=lnk[w][ind];
	segsb.upd(l,-1);
	segpb.upd(maxh-l,-1);
}
 
void insc(int w,int ind){
	int l=lnk[w][ind];
	segsc.upd(l,-1);
	segpc.upd(maxh-l,-1);
}
 
void eraseb(int w,int ind){
	int l=lnk[w][ind];
	segsb.upd(l,1);
	segpb.upd(maxh-l,1);
}
 
void erasec(int w,int ind){
	int l=lnk[w][ind];
	segsc.upd(l,1);
	segpc.upd(maxh-l,1);
}
 
bool ch(){
	if(segpc.ps[1]<0||segsb.ps[1]<0||segsc.ps[1]<0||segpb.ps[1]<0){
		return 0;
	}
	return 1;
}
 
bool check(int mid){
	clear();
	int l=0,r=0;
	for(int i=0;i<n;i++){
		while(l<sz&&alla[l]<allb[i]-mid){
			l++;
		}
		inssufb(l);
		while(r<sz&&alla[r]<=allb[i]+mid){
			r++;
		}
		inspsb(r-1);
	}
	l=0,r=0;
	for(int i=0;i<n;i++){
		while(l<sz&&alla[l]<allc[i]-mid){
			l++;
		}
		inssufc(l);
		while(r<sz&&alla[r]<=allc[i]+mid){
			r++;
		}
		inspsc(r-1);
	}
	for(int i=0;i<n;i++){
		insb(i,0);
		insc(i,1);
	}
	for(int i=0,j=n-1;i<n;i++,j--){
		if(ch()==1){
			return 1;
		}
		eraseb(i,0);
		erasec(j,1);
		insb(j,1);
		insc(i,0);
	}
	return ch();
}
 
int solve(){
	int low=-1,high=1e9+5,mid;	
	while(high-low>1){
		mid=(high+low)/2;
		if(check(mid)){
			high=mid;
		}else{
			low=mid;
		}
	}	
	return high;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();
	int mainres=inf;
	mainres=solve();
	swap(allb,allc);
	mainres=min(mainres,solve());
	cout<<mainres<<"\n";
}

Compilation message (stderr)

Main.cpp: In function 'void fastscan(int&)':
Main.cpp:36:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   36 |     register int c;
      |                  ^

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