83pts 求助!
查看原帖
83pts 求助!
700122
hnxxwpf楼主2024/3/3 19:36
#include<iostream>
#include<stack>
#define ll long long
using namespace std;
ll n,pos,cnt,limit,h[1000001],vis[1000001];
stack<pair<ll,ll> > st;
int main(){
	scanf("%I64d",&n);
	for(int i = 0;i < n;++i){
		scanf("%I64d",&h[i]);
		if(h[i] > h[pos]) pos = i;
	}
	for(int i = pos;i < n;++i){
		while(!st.empty() && h[i] > st.top().first){
			cnt += st.top().second;
			st.pop();
		}
		if(!st.empty() && st.top().first == h[i]){
			ll t = st.top().second;
			cnt += t + (st.size() >= 2);
			st.pop();
			if(st.size()>=2 && st.top().first == h[pos]) vis[i] = 1;
			st.push(make_pair(h[i],t+1));
		}else{
			if(!st.empty()){
				cnt++;
				if(st.top().first == h[pos]) vis[i] = 1;
			}
			st.push(make_pair(h[i],1));
		}
	}
	for(int i = 0;i < pos;++i){
		while(!st.empty() && h[i] > st.top().first){
			cnt += st.top().second;
			st.pop();
		}
		if(!st.empty() && st.top().first == h[i]){
			ll t = st.top().second;
			cnt += t + (st.size() >= 2);
			if(st.size()>=2 && st.top().first == h[pos]) vis[i] = 1;
			st.pop();
			st.push(make_pair(h[i],t+1));
		}
		else{
			if(!st.empty()){
				cnt++;
				if(st.top().first == h[pos]) vis[i] = 1;
			}
			st.push(make_pair(h[i],1));
		}
	}
	for(int i = pos-1;i >= 0;--i){
		if(!vis[i] && h[i]!=h[pos] && h[i]>=limit) cnt++; 
		limit = max(limit,h[i]);
	}
	for(int i = n-1;i > pos;--i){
		if(!vis[i] && h[i]!=h[pos] && h[i]>=limit) cnt++;
		limit = max(limit,h[i]);
	}
	printf("%I64d",cnt);
	return 0;
}

2024/3/3 19:36
加载中...