fork download
copy 
  1. // trust yourself ba2a ysta
  2. // hategy kda kda
  3. // lw m4 elnhrda , bokra ^_^
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. using ll = long long;
  7. #define sz(st) int(st.size())
  8. #define all(st) st.begin(), st.end()
  9.  
  10. const int MAX_N = 1e5 + 10;
  11. int seg[(MAX_N * 4)]; // fill with -1
  12. int tree_size = 1;
  13.  
  14.  
  15. void update(int idx, int val)
  16. {
  17.     idx += tree_size;
  18.     seg[idx] = max(seg[idx], val);
  19.     for (idx /= 2;idx >= 1;idx /= 2)
  20.         seg[idx] = max(seg[idx * 2], seg[idx * 2 + 1]);
  21. }
  22.  
  23. int query(int L, int R)
  24. {
  25.     L += tree_size, R += tree_size;
  26.     int ret = -1;
  27.     while (L <= R)
  28.     {
  29.         if (L & 1) ret = max(ret, seg[L++]);
  30.         if (!(R & 1)) ret = max(ret, seg[R--]);
  31.         L /= 2, R /= 2;
  32.     }
  33.     return ret;
  34. }
  35.  
  36.  
  37.  
  38. void Solve()
  39. {
  40.     int n; cin >> n;
  41.  
  42.     vector < int > a(n + 1);
  43.  
  44.     for (int i = 1;i <= n;i++)
  45.         cin >> a[i];
  46.  
  47.     vector < int > temp = a;
  48.     sort(all(temp));
  49.     temp.erase(unique(all(temp)), temp.end());
  50.     for (int i = 1;i <= n;i++)
  51.     {
  52.         a[i] = upper_bound(all(temp), a[i]) - temp.begin();
  53.     }
  54.  
  55.     while (tree_size < sz(a))
  56.         tree_size *= 2;
  57.  
  58.  
  59.  
  60.     deque < int > ans;
  61.  
  62.     for (int i = n; i >= 1; i--)
  63.     {
  64.         int cur_val = a[i];
  65.  
  66.         int less_idx = query(1, cur_val - 1);
  67.  
  68.         if (~less_idx) ans.push_front(abs(less_idx - i - 1));
  69.         else ans.push_front(-1);
  70.  
  71.         update(cur_val, i);
  72.     }
  73.  
  74.  
  75.     for (auto i : ans)
  76.     {
  77.         cout << i << " ";
  78.     }
  79.  
  80. }
  81.  
  82. signed main()
  83. {
  84. #if LOCAL
  85.     freopen("input.txt", "r", stdin);
  86.     freopen("output.txt", "w", stdout);
  87. #endif
  88.     ios_base::sync_with_stdio(false);
  89.     cin.tie(nullptr);
  90.     int t = 1;
  91.     //cin >> t;
  92.     fill(seg, seg + (MAX_N * 4), -1);
  93.     for (int tc = 1; tc <= t; tc++) {
  94.         Solve();
  95.         cout << "\n";
  96.     }
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6
10 8 5 3 50 45
stdout
copy 
2 1 0 -1 0 -1
https://ideone.com/ZGoRAw
language:
C++ (gcc 8.3)
created:
5 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!