fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int maxn = 2e5 + 5;
  5. const int mod = 1e9 + 7;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, pair<int, int>> iii;
  8. #define fi first
  9. #define se second
  10. #define read(_a, n)              \
  11.     for (int i = 1; i <= n; i++) \
  12.     cin >> _a[i]
  13. #define For(i, _a, _b) for (int i = _a; i <= _b; i++)
  14. #define fastIO                        \
  15.     ios_base::sync_with_stdio(false); \
  16.     cin.tie(0);                       \
  17.     cout.tie(0);
  18. #define File(_x, _y)    \
  19.     if (fopen(_x, "r")) \
  20.     freopen(_x, "r", stdin), freopen(_y, "w", stdout)
  21. #define file "main"
  22. #define bit(x, i) ((x >> i) & 1)
  23. #define bat(x, i) (x | (1 << i))
  24. #define dem(x) __builtin_popcountll(x)
  25.  
  26. int f[maxn][23], n, a[maxn], res;
  27.  
  28. int get(int l, int r)
  29. {
  30.     if (r < l)
  31.         return 0;
  32.     int k = 31 - __builtin_clz(r - l + 1);
  33.     return max(f[l][k], f[r - (1 << k) + 1][k]);
  34. }
  35.  
  36. int32_t main()
  37. {
  38.     fastIO;
  39.     // File(file ".inp", file ".out");
  40.     cin >> n;
  41.     for (int i = 1; i <= n; i++)
  42.         cin >> a[i], f[i][0] = a[i];
  43.     for (int k = 1; k <= 20; k++)
  44.     {
  45.         for (int i = 1; i + (1 << k) - 1 <= n; i++)
  46.         {
  47.             f[i][k] = max(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
  48.         }
  49.     }
  50.     for (int i = 1; i < n; i++)
  51.     {
  52.         int maxx = get(i, n);
  53.         int l = i + 1, r = n;
  54.         int ans = i;
  55.         while (l <= r)
  56.         {
  57.             int mid = (l + r) >> 1;
  58.             if (get(i + 1, mid - 1) < maxx)
  59.                 l = mid + 1, ans = mid;
  60.             else
  61.                 r = mid - 1;
  62.         }
  63.         if (get(i + 1, ans - 1) < maxx)
  64.             res += ans - i; // cout << ans-i << " " << maxx << endl;
  65.     }
  66.     cout << res;
  67. }
  68.  
Success #stdin #stdout 0s 5516KB
comments (?)
stdin
copy 
5
5 1 2 4 3
stdout
copy 
8
https://ideone.com/x4EPUl
language:
C++14 (clang 8.0)
created:
9 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!