fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define N 100000
  3. using namespace std;
  4. int a[N+3],x[N+3], pos[N+3];
  5. int n;
  6. int TL[N+3], TR[N+3];
  7. int L[N+3], R[N+3];
  8.  
  9. int get(int k, int *T)
  10. {
  11.     int s = 0;
  12.     for (; k > 0; k -= k & (-k)) s += T[k];
  13.     return s;
  14. }
  15.  
  16. void update(int k, int val, int *T)
  17. {
  18.     for (; k <= n; k += k & (-k)) T[k] += val;
  19. }
  20. int main()
  21. {
  22.     freopen("sapxep.inp","r",stdin);
  23.     freopen("sapxep.out","w",stdout);
  24.     cin >> n;
  25.     for (int i=1; i<=n; i++)
  26.     {
  27.         cin >> a[i];
  28.         pos[a[i]] = i;
  29.     }
  30.     int d = 0;
  31.     for (int i=1; i<=n/2; i++)
  32.     {
  33.         x[pos[i]] = ++d;
  34.         x[pos[n-i+1]] = ++d;
  35.     }
  36.     for (int i=1; i<=n; i++)
  37.     {
  38.         if (n % 2 == 1 && a[i] == n/2 + 1) continue;
  39.         L[i] = get(x[i] - 1, TL);
  40.         update(x[i],1,TL);
  41.     }
  42.     for (int i=n; i>0; i--)
  43.     {
  44.         if (n % 2 == 1 && a[i] == n/2 + 1) continue;
  45.         R[i] = get(x[i] - 1, TR);
  46.         update(x[i],1,TR);
  47.     }
  48.     for (int i=1; i<=n/2; i++)
  49.     {
  50.         int j = pos[i];
  51.         if (a[j] <= n/2) cout << j - 1 - L[j] << '\n';
  52.         else cout << n - j - R[j] << '\n';
  53.         j = pos[n-i+1];
  54.         if (a[j] <= n/2) cout << j - 1 - L[j] << '\n';
  55.         else cout << n - j - R[j] << '\n';
  56.     }
  57.     if (n % 2 == 1) cout << 0;
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ie2d2g
Sapxep
language:
C++14 (gcc 8.3)
created:
2 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!