fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define el '\n'
  3. using namespace std;
  4. typedef long long ll;
  5. void fastip()
  6. {
  7.     ios_base::sync_with_stdio(0);
  8.     cin.tie(0); cout.tie(0);
  9. }
  10. int main(){
  11.     fastip();
  12.     int n;
  13.     cin >> n;
  14.     vector<int> a(n+1);
  15.     vector<ll> cpair(n+1, 0), re(n+1, 0);
  16.     stack<int> s;
  17.     ll cnt=0;
  18.     for (ll i=1; i<=n; i++){
  19.         cin >> a[i];
  20.         while (!s.empty() && a[i]>=a[s.top()]){
  21.             if(a[i]==a[s.top()]) re[i]= re[s.top()] +1;
  22.             cpair[i]+= re[s.top()] +1;
  23.             s.pop();
  24.         }
  25.         if (!s.empty() && a[i]<a[s.top()]) cpair[i]++;
  26.         cnt+=cpair[i];
  27.         s.push(a[i]);
  28.     }
  29.     cout << cnt;
  30.     return 0;
  31. }
  32.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5381
https://ideone.com/k3w5YT
language:
C++ (gcc 8.3)
created:
40 days 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!