求助90分找hack(悬3关注)
查看原帖
求助90分找hack(悬3关注)
235901
Always_Remember_It楼主2023/9/17 17:24
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int N=4e5+10;
int n,h[N],nxt[N];
int num,in[N],l[N],r[N],s[N],t[N];
void block(){
	num=sqrt(n);
	if(num*num!=n) ++num;
	int lar=num;
	if(num*(num-1)>=n&&num*num!=n) --lar;
	for(int i=1;i<num;i++){
		l[i]=r[i-1]+1;
		r[i]=i*lar;
	}
	l[num]=r[num-1]+1;
	r[num]=n;
	for(int i=1;i<=r[num-1];i++){
		in[i]=(i-1)/lar+1;
	}
	for(int i=l[num];i<=n;i++){
		in[i]=num;
	}
	for(int i=1;i<=num;i++){
		for(int j=l[i];j<=r[i];j++){
			if(h[j]>s[i]){
				s[i]=h[j];
				t[i]=j;
			}
		}
	}
}
int ask(int lt,int rt){
	int res=0,pt=0;
	if(in[lt]==in[rt]){
		for(int i=lt;i<=rt;i++){
			if(h[i]>res){
				res=h[i];
				pt=i;
			}
		}
		return pt;
	}
	for(int i=lt;i<=r[in[lt]];i++){
  		if(h[i]>res){
  			res=h[i];
  			pt=i;
		}
	}
	for(int i=in[lt]+1;i<in[rt];i++){
  		if(s[i]>res){
  			res=s[i];
  			pt=t[i];
		}
	}
	for(int i=l[in[rt]];i<=rt;i++){
  		if(h[i]>res){
  			res=h[i];
  			pt=i;
		}
	}
	return pt;
}
int main(){
	cin>>n;
	if(n==1) while(1);
	for(int i=1;i<=n;i++){
		cin>>h[i];
		//if(h[i]==0) while(1);
	}
	//cout<<0;
	//return 0;
	block();
	for(int i=n;i>=1;i--){
		nxt[i]=max(nxt[i+1],h[i]);
	}
	int l1=1,r1=2,maxn=0;
	while(r1<=n){
	    if(l1>r1) while(1);
		if(l1==r1){
			++r1;
			//continue;
		}
		if(h[r1]<=h[l1]){
		//	if(r1-l1<=1){
			//	++l1;
			///	++r1;
			//	continue;
		//	}
			int now=0,ps=ask(l1,r1);
			
			if(ps!=l1)maxn=max(maxn,ps-l1+1);
			++l1;
			continue;
		}
		if(h[r1]==nxt[l1]){
			maxn=max(maxn,r1-l1+1);
			l1=r1+1;
			++r1;
			continue;
		}
		++r1;
	}
	//maxn=max(maxn,n-l1+1);
	if(maxn<=1) cout<<0;
	else cout<<maxn<<endl;
	return 0;
}
2023/9/17 17:24
加载中...