Helicator

shift.cpp

Dec 8th, 2021
989
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #include <ext/pb_ds/assoc_container.hpp> // Common file
  5. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  6. using namespace __gnu_pbds;
  7. template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;
  8.  
  9. #define int long long
  10. #define vi vector<int>
  11. #define ii pair<int,int>
  12. #define fi first
  13. #define sc second
  14. #define stoi stoll
  15. #define popcnt __builtin_popcount
  16. #define getbit(x, k) ((x >> k) & 1)
  17. #define all(x) (x).begin(),(x).end()
  18. #define FOR(i,j,k) for(int i=j; i<k; i++)
  19. #define look(a) cerr <<#a<<": "<<a<<endl;
  20. #define look2(a,b) cerr <<#a<<": "<<a<<" | "<<#b<<": "<<b<< endl;
  21.  
  22. void solve()
  23. {
  24.     int n;
  25.     cin >> n;
  26.     int a[n];
  27.     int ans = 0;
  28.     ordered_set<int> s;
  29.     FOR(i,0,n) {
  30.         cin >> a[i];
  31.         ans += s.size() - s.order_of_key(a[i]);
  32.         s.insert(a[i]);
  33.     }
  34.     cout << ans << '\n';
  35.     FOR(i,0,n-1){
  36.         ans -= a[i];
  37.         ans += n - a[i] - 1;
  38.         cout << ans << '\n';
  39.     }
  40. }
  41.  
  42. signed main()
  43. {
  44.     cin.tie(0)->sync_with_stdio(0);
  45.     freopen("in", "r", stdin);
  46.     freopen("out", "w", stdout);
  47.     int T = 1;
  48.     // cin >> T;
  49.     while (T--) {
  50.         solve();
  51.         cout << '\n';
  52.     }
  53.     cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  54. }
RAW Paste Data