fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
  4. #define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
  5. #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
  6. #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
  7. #define ALL(v) (v).begin(),(v).end()
  8. #define pb push_back
  9. #define mp make_pair
  10. #define fi first
  11. #define se second
  12. #define SZ(x) ((int)(x).size())
  13. #define double db
  14. typedef long long ll;
  15. typedef pair<int,int> PII;
  16. const ll mod=1000000007;
  17. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  18. const int MAXN = 1E6+3;
  19. const int oo = 1e9+3;
  20.  
  21. int n, i, j, a[MAXN], c[MAXN], s[MAXN], top, tmp;
  22. ll ans;
  23.  
  24. int main() {
  25.         ios_base::sync_with_stdio(0); cin.tie(0);
  26.     	#ifndef ONLINE_JUDGE
  27.     	freopen("test.inp", "r", stdin);
  28.     	freopen("test.out", "w", stdout);
  29.     	#endif //yeulaptrinh.pw
  30.     cin >> n;
  31.     FOR(i,1,n) cin >> a[i];
  32.  
  33.     top = 0;
  34.     FOR(i,1,n) {
  35.         tmp = 1;
  36.         while (top&&s[top]<=a[i]) {
  37.             ans += c[top];
  38.             if (s[top]==a[i]) tmp += c[top];
  39.             c[top] = 0; top--;
  40.         }
  41.         if (top) ans++;
  42.         // push
  43.         top++;
  44.         s[top] = a[i];
  45.         c[top] = tmp;
  46.     }
  47.     cout << ans;
  48. 	return 0;
  49. }
Success #stdin #stdout 0s 26952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/raQ89G
language:
C++ (gcc 8.3)
created:
6 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!