Submission #988468

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

Main

#include<bits/stdc++.h>
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3,unroll-loops")
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(){
	//cin>>n;
	fastscan(n);
	alla.push_back(-1);
	for(int i=0;i<n;i++){
		//cin>>all[i][0];
		fastscan(all[i][0]);
		alla.push_back(all[i][0]);
	}
	for(int i=n-1;i>=0;i--){
		//cin>>all[i][1];
		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++){
	//	cin>>allb[i];
		fastscan(allb[i]);
	}
	for(int i=0;i<n;i++){
		//cin>>allc[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);
	auto start = std::chrono::high_resolution_clock::now();
//	freopen("inp.txt","r",stdin);
	vorod();
//	auto end = std::chrono::high_resolution_clock::now();
  //  std::chrono::duration<double> duration = end - start;
    //std::cout << "vorod time: " << duration.count() << " seconds." << std::endl;
	int mainres=inf;
	mainres=solve();
	swap(allb,allc);
	mainres=min(mainres,solve());
	cout<<mainres<<"\n";
//    end = std::chrono::high_resolution_clock::now();
  // 	duration = end - start;
    //std::cout << "Execution time: " << duration.count() << " seconds." << std::endl;
}

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;
      |                  ^
Main.cpp: In function 'int main()':
Main.cpp:182:7: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  182 |  auto start = std::chrono::high_resolution_clock::now();
      |       ^~~~~

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