Advertisement
esraa_syam

Untitled

Jul 17th, 2023
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.48 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define nl "\n"
  3. #define fi first
  4. #define se second
  5. #define pi 3.14159
  6. #define ll long long
  7. #define odd(a)  (a&1)
  8. #define even(a)  !(a&1)
  9. #define Mod 1'000'000'007
  10. #define INF 2'000'000'000
  11. #define sz(x) int(x.size())
  12. #define charToInt(s) (s - '0')
  13. #define ull unsigned long long
  14. #define number_line iota(all(vec) , 1)
  15. #define all(s) s.begin(), s.end()
  16. #define rall(v) v.rbegin() , v.rend()
  17. #define fixed(n) fixed << setprecision(n)
  18. #define Num_of_Digits(n) ((int)log10(n) + 1)
  19. #define to_decimal(bin) stoll(bin, nullptr, 2)
  20. #define Ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))
  21. #define Floor(n, m) (((n) / (m)) - ((n) % (m) ? 0 : 1))
  22. #define Upper(s) transform(all(s), s.begin(), ::toupper);
  23. #define Lower(s) transform(all(s), s.begin(), ::tolower);
  24. #define cout_map(mp) for(auto& [f, s] : mp) cout << f << "  " << s << "\n";
  25. //  ----- bits-------
  26. #define pcnt(n) __builtin_popcount(n)  
  27. #define pcntll(n) __builtin_popcountll(n)
  28. #define clz(n) __builtin_clz(n)    // <---100
  29. #define clzll(n) __builtin_clzll(n)
  30. #define ctz(n) __builtin_ctz(n)  // 0001---->
  31. #define ctzll(n) __builtin_ctzll(n)
  32.  
  33. using namespace std;
  34.  
  35. template < typename T = int > istream& operator >> (istream &in, vector < T > & v){
  36.     for(auto & x : v) in >> x;
  37.     return in;
  38. }
  39.  
  40. template < typename T = int > ostream& operator << (ostream &out, const vector < T > & v){
  41.     for(const T & x : v) out << x << nl;
  42.     return out;
  43. }
  44.  
  45. void esraa()
  46. {
  47.    // freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  48.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  49. #ifndef ONLINE_JUDGE
  50.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  51. #endif
  52. }
  53.  
  54. typedef int item;
  55. struct segtree{
  56.     int size;
  57.     vector < item > values;
  58.     item NEUTRAL_ELEMENT = 0;
  59.  
  60.     item merge(item a , item b){
  61.         return a + b;
  62.     }
  63.  
  64.     item single(int v){
  65.         return v;
  66.     }
  67.  
  68.     void init(int n){
  69.         size = 1;
  70.         while(size < n) size *= 2;
  71.         values.resize(2 * size);
  72.     }
  73.  
  74.     void build(vector < ll > &a , int x , int lx , int rx){
  75.         if(rx - lx == 1){
  76.             if(lx < sz(a)) values[x] = single(a[lx]);
  77.             return;
  78.         }
  79.         int m = (lx + rx) / 2;
  80.         build(a , 2 * x + 1 , lx , m);
  81.         build(a , 2 * x + 2 , m , rx);
  82.         values[x] = merge(values[2 * x + 1] , values[2 * x + 2]);
  83.     }
  84.  
  85.     void build(vector < ll > &a){
  86.         build(a , 0 , 0 , size);
  87.     }
  88.  
  89.     void set(int i , int v , int x , int lx , int rx){
  90.         if(rx - lx == 1){
  91.             values[x] = single(v);
  92.             return;
  93.         }
  94.  
  95.         int m = (lx + rx) / 2;
  96.         if(i < m) set(i , v , 2 * x + 1 , lx , m);
  97.         else set(i , v , 2 * x + 2 , m , rx);
  98.         values[x] = merge(values[2 * x + 1] , values[2 * x + 2]);
  99.     }
  100.  
  101.     void set(int i , int v){
  102.         set(i , v , 0 , 0 , size);
  103.     }
  104.  
  105.     item calc(int l , int r , int x , int lx , int rx){
  106.         if(lx >= r or l >= rx) return NEUTRAL_ELEMENT;
  107.         if(lx >= l and rx <= r) return values[x];
  108.         int m = (lx + rx) / 2;
  109.         item s1 = calc(l , r , 2 * x + 1 , lx , m);
  110.         item s2 = calc(l , r , 2 * x + 2 , m , rx);
  111.         return merge(s1 , s2);
  112.     }
  113.  
  114.     item calc(int l , int r){
  115.         return calc(l , r , 0 , 0 , size);
  116.     }
  117.  
  118.     int find(int k , int x , int lx , int rx){
  119.         if(rx - lx == 1) return lx;
  120.         int m = (lx + rx) / 2;
  121.         int sl = values[2 * x + 1];
  122.         if(k < sl) return find(k , 2 * x + 1 , lx , m);
  123.         else return find(k - sl , 2 * x + 2 , m , rx);
  124.     }
  125.  
  126.     int find(int k){
  127.         return find(k , 0 , 0 , size);
  128.     }
  129.  
  130.     int first_above(int v , int l , int x , int lx , int rx){
  131.         if(values[x] < v) return -1;
  132.         if(rx <= l) return -1;
  133.         if(rx - lx == 1) return lx;
  134.         int m = (lx + rx) / 2;
  135.         int res = first_above(v , l , 2 * x + 1 , lx , m);
  136.         if(res == -1) res = first_above(v , l , 2 * x + 2 , m , rx);
  137.         return res;
  138.     }
  139.  
  140.     int first_above(int v , int l){
  141.         return first_above(v , l , 0 , 0 , size);
  142.     }
  143.  
  144. };
  145.  
  146. void solve(){
  147.     int n;
  148.     cin >> n;
  149.     vector < ll > a(n);
  150.     cin >> a;
  151.     segtree st;
  152.     st.init(n);
  153.     for(int i = 0 ; i < n ; i++){
  154.         cout << st.calc(a[i] , n) << " ";
  155.         st.set(a[i] - 1 , 1);
  156.     }
  157. }
  158. int main()
  159. {
  160.     esraa();
  161.     int t = 1;
  162.    // cin >> t;
  163.     //cin.ignore();
  164.     while(t--)
  165.       solve();
  166.     return 0;
  167. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement