General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
62057917 Practice:
wyxdrqc
5E - 9 C++14 (GCC 6-32) Accepted 560 ms 29688 KB 2019-10-07 15:42:32 2019-10-07 15:42:32
→ Source
#include<cstdio>
#include<iostream>
#include<cctype>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 1e6 + 3;
int a[N],pre[N],suf[N];
int n;
int s[N],top;
LL g[N];
vector <int> G;
int main(){
	int pos = 0,maxx = 0;
	scanf("%d",&n);
	for(int i = 1;i <= n;++i){
		scanf("%d",&a[i]);
		if(a[i] > maxx) maxx = a[i],pos = i;	
	}
	for(int i = pos + 1;i <= n;++i) G.push_back(a[i]);
	for(int i = 1;i < pos;++i) G.push_back(a[i]);
	LL ans = 0;
	for(int i = 0;i < (int)G.size();++i) pre[i + 1] = max(pre[i],G[i]);
	for(int i = G.size() - 1;i >= 0;--i) suf[i + 1] = max(suf[i + 2],G[i]);
	for(int i = 1;i < n;++i) if(pre[i] == G[i - 1] || suf[i] == G[i - 1]) ans++;
	for(int i = 0;i < (int)G.size();++i){
		int cnt = 0;
		while(top && G[s[top]] <= G[i]){
			if(G[s[top]] == G[i]) cnt += g[top];
			top--;	
		}
		ans += cnt;
		if(top) ans ++;
		s[++top] = i;
		g[top] = cnt + 1;
	}
	top = 0;
	for(int i = G.size() - 1;i >= 0;--i){
		while(top && G[s[top]] <= G[i]) top--;	
		if(top) ans++;
		s[++top] = i;
	}
	printf("%lld\n",ans);
	return 0;	
}
/*
10
2 2 2 1 1 2 2 2 1 2
*/ 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details