TLE 90分求助
查看原帖
TLE 90分求助
924166
shiranai楼主2023/8/9 20:52

TLE了第9个点,其他AC,求各位指正

#include <iostream>
#include <stdlib.h>
#define N 100000

using namespace std;

struct {
	int elem[N];
	int elem_num;
} stack;

int cows[N],n,l[N],r[N],pos;
//l:左边第一个大的 r:右边第一个小的 

int push_stack_l(){
	while(stack.elem_num>0 && cows[stack.elem[stack.elem_num-1]]<cows[pos]) stack.elem_num--;
	if(!stack.elem_num){
		stack.elem[stack.elem_num++]=pos;
		return -1;
	}
	stack.elem[stack.elem_num++]=pos;
	return stack.elem[stack.elem_num-2];
}

int push_stack_r(){
	while(stack.elem_num>0 && cows[stack.elem[stack.elem_num-1]]>cows[pos]) stack.elem_num--;
	if(!stack.elem_num){
		stack.elem[stack.elem_num++]=pos;
		return -1;
	}
	stack.elem[stack.elem_num++]=pos;
	return stack.elem[stack.elem_num-2];
}

void process_l(){
	pos=0;
	stack.elem_num=0;
	while(pos<n) {l[pos]=push_stack_l();pos++;
	}
}

void process_r(){
	pos=n-1;
	stack.elem_num=0;
	while(pos>=0) {r[pos]=push_stack_r();pos--;
	}
}

void input(){
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>cows[i];
	process_l();
	process_r();
}

void output(){
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=(r[i]==-1?n-1:r[i]-1);j>=i+ans;j--){
			if(j-i+1<=ans) break;
			if(l[j]<i){
				ans=j-i+1;
				break;
			}
		}
	}
	cout<<(ans==1?0:ans);
}

int main(){
	input();
	output();
	return 0;
}
2023/8/9 20:52
加载中...