fork download
copy 
  1. #define taskname "sort"
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7. const int maxN = 1e5 + 1;
  8. int n, a[maxN], id[maxN];
  9.  
  10. int main()
  11. {
  12.     ios_base::sync_with_stdio(false);
  13.     cin.tie(nullptr);
  14.     //freopen(taskname".in", "r", stdin);
  15.     //freopen(taskname".out", "w", stdout);
  16.     cin >> n;
  17.     if (n == 1)
  18.     {
  19.         cout << "0\n";
  20.         return 0;
  21.     }
  22.     for (int i = 1; i <= n; ++i)
  23.     {
  24.         cin >> a[i];
  25.         id[i] = i;
  26.     }
  27.     for (int i = 1; i < n; ++i)
  28.         if (a[i] > a[i + 1])
  29.             swap(a[i], a[i + 1]);
  30.     stable_sort(id + 1, id + n + 1, [](int i, int j)
  31.     {
  32.         return a[i] < a[j];
  33.     });
  34.     long long res = n;
  35.     int MaxIdx = 0;
  36.     for (int i = 1; i <= n; ++i)
  37.     {
  38.         int j = id[i];
  39.         if (MaxIdx < j)
  40.         {
  41.             MaxIdx = j;
  42.             res += MaxIdx - i;
  43.         }
  44.         else
  45.             res += MaxIdx - (i - 1);
  46.     }
  47.     cout << res;
  48. }
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
7
20
2
3
4
9
8
7
stdout
copy 
12
https://ideone.com/agAsKt
language:
C++14 (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!