fork(1) download
copy 
  1. #include<cstdio>
  2. #include<stack>
  3. #include<ctime>
  4. #include<cstdlib>
  5. #define MX 500006
  6. #define LL long long
  7. using namespace std;
  8. int N,nxt[MX],cm[MX],ar[MX],nx[MX];
  9.  
  10. int main(){
  11.     int T;
  12.     scanf("%d",&T);
  13.     while(T--){
  14.         scanf("%d",&N);
  15.         for(int i=0;i<N;i++) scanf("%d",&ar[i]);
  16.         stack<int> S,G;
  17.         for(int i=0;i<N;i++){
  18.             while(!S.empty() && ar[S.top()]<ar[i]) nxt[S.top()]=i,S.pop();
  19.             S.push(i);
  20.         }
  21.         while(!S.empty()) nxt[S.top()]=-1,S.pop();
  22.         for(int i=0;i<N;i++){
  23.             while(!G.empty() && ar[G.top()]<=ar[i]) nx[G.top()]=i,G.pop();
  24.             G.push(i);
  25.         }
  26.         while(!G.empty()) nx[G.top()]=-1,G.pop();
  27.         LL ans=0;
  28.         for(int i=N-1;i>=0;i--){
  29.             if(nxt[i]==-1) ans+=(N-i-1);
  30.             else ans+=(nxt[i]-i-1)+cm[nxt[i]];
  31.             if(nx[i]==-1) cm[i]=1;
  32.             else cm[i]=cm[nx[i]]+1;
  33.         }
  34.         printf("%lld\n",ans);
  35.         /*LL ch=0;
  36.         for(int i=0;i<N;i++){
  37.             int mx=ar[i];
  38.             for(int j=i+1;j<N;j++){
  39.                 mx=max(mx,ar[j]);
  40.                 if(mx<=max(ar[i],ar[j])) ++ch;
  41.             }
  42.         }
  43.         printf("%lld\n",ch);*/
  44.     }
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 10808KB
comments (?)
stdin
copy 
1
5
1 2 3 4 5
stdout
copy 
10
https://ideone.com/tfAats
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!