fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define pub push_back
  7. #define pob pop_back
  8. #define mpa make_pair
  9. #define endl '\n'
  10. #define BIT(i) ((1 << i))
  11. const int maxn = 1e5 + 10;
  12. int c, n, k;
  13. int a[maxn];
  14. int f[maxn];
  15. void update(int id, int val)
  16. {
  17.     while(id <= n)
  18.     {
  19.         f[id] += val;
  20.         id += (id & -id);
  21.     }
  22. }
  23. int get(int id)
  24. {
  25.     if(id > n) return 0;
  26.     int res = 0;
  27.     while(id > 0)
  28.     {
  29.         res += f[id];
  30.         id -= (id & -id);
  31.     }
  32.     return res;
  33. }
  34. ll ans[maxn];
  35. int L[maxn], R[maxn];
  36. int d[maxn];
  37. int main()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0);
  41.     cout.tie(0);
  42.     #define code code
  43. //    freopen("code.INP","r",stdin);
  44. //    freopen("code.OUT","w",stdout);
  45.     cin >> c >> n >> k;
  46.     int pos = 0;
  47.     for(int i=1; i<=n; i++)
  48.     {
  49.         cin >> a[i];
  50.     }
  51.     for(int i=1; i<=n; i++)
  52.     {
  53.         L[a[i]] = get(a[i]);
  54.         update(a[i], 1);
  55.     }
  56.     for(int i=1; i<=n; i++) update(i, -1);
  57.     for(int i=n; i>=1; i--)
  58.     {
  59.         R[a[i]] = get(a[i]);
  60.         update(a[i], 1);
  61.     }
  62.     for(int i=2; i<=n; i++)
  63.     {
  64.         d[i] = L[i] - R[i];
  65.     }
  66.     d[1] = 1e9;
  67.     sort(d + 1, d + n + 1);
  68. //    for(int i=1; i<=n; i++) cout << d[i] << " ";
  69. //    cout << endl;
  70.     for(int i=1; i<=n; i++) ans[1] += R[i];
  71.     for(int i=2; i<=n + 1; i++)
  72.     {
  73.         ans[i] = ans[i - 1] + d[i - 1];
  74.     }
  75.     if(c == 1)
  76.     {
  77.         cout << ans[k];
  78.     }
  79.     else
  80.     {
  81.         for(int i=1; i<=n; i++) cout << ans[i] << " ";
  82.     }
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/hVNJE7
language:
C++14 (clang 8.0)
created:
16 hours 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!