fork download
copy 
  1.  
  2.  
  3.  
  4. #include<iostream>
  5. #include<vector>
  6. #include<map>
  7. #include<unordered_map>
  8. #include<set>
  9. #include<unordered_set>
  10. #include<string>
  11. #include<algorithm>
  12. #include<queue>
  13. #include<ext/pb_ds/tree_policy.hpp>
  14. #include<ext/pb_ds/assoc_container.hpp>
  15. using namespace __gnu_pbds;
  16. #define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  17.  
  18. using namespace std;
  19. #define M 200005
  20. #define MM 10000000001
  21. #define ll long long
  22. #define mll map<ll,ll>
  23. #define f(b) for(ll i=0;i<b;i++)
  24. #define fj(b) for(ll j=0;j<b;j++)
  25. #define rf(b) for(ll i=b;i>-1;i--)
  26. #define fr(a,b) for(ll i=a;i<b;i++)
  27. #define rfr(a,b) for(ll i=a;i>b;i--)
  28. #define pb push_back
  29. #define F first
  30. #define S second
  31. #define dd long double
  32. #define mp make_pair
  33. #define pii pair<ll,ll>
  34. #define vi vector<ll>
  35. #define vp vector<pair<ll,ll> >
  36. #define endl "\n"
  37. #define seea(a,n) for(ll i=0;i<n;i++){cin>>a[i];}
  38. #define ya cout<<"YES"<<"\n";
  39. #define na cout<<"NO"<<"\n";
  40. #define pr cout<<disp<<"\n";
  41. #define pri cout<<disp<<" ";
  42. #define nl cout<<"\n";
  43.  
  44.  
  45.  
  46. vector<ll> a, sg;
  47. void build(int l, int r, int node){
  48.     if(l==r){
  49.         sg[node]=a[l];return;
  50.     }
  51.     int m = (l+r)/2;
  52.     build(l, m, 2*node);
  53.     build(m+1, r, 2*node+1);
  54.     sg[node]=max(sg[2*node], sg[2*node+1]);
  55. }
  56. void upd(int idx, ll val, int tl, int tr, int node){
  57.     if(tr<idx||tl>idx) return;
  58.     if(tl==idx&&tr==idx){
  59.         sg[node]=val;return;
  60.     }
  61.     int tm = (tl+tr)/2;
  62.     upd(idx, val, tl, tm, 2*node);
  63.     upd(idx, val, tm+1, tr, 2*node+1);
  64.     sg[node]=max(sg[2*node], sg[2*node+1]);
  65. }
  66. ll query(int l, int r, int tl, int tr, int node){
  67.     if(tr<l||tl>r) return 0;
  68.     if(l<=tl&&tr<=r){
  69.         return sg[node];
  70.     }
  71.     int tm = (tl+tr)/2;
  72.     return max(query(l, r, tl, tm, 2*node), query(l, r, tm+1, tr, 2*node+1));
  73. }
  74. void Solve()
  75. {
  76.     ll n, m;
  77.     cin >> n >> m;
  78.     int sz = n+1;
  79.     a.assign(sz, 0);
  80.     sg.assign(4*sz, 0);
  81.     for(int i =1;i<sz;i++){
  82.         cin>>a[i];
  83.  
  84.     }
  85.     build(1, n, 1);
  86. 	oset o;
  87.     for(int q =0;q<m;q++){
  88.         ll val;
  89.         cin>>val;
  90.         int l = 1, r = n;
  91.         int ans = 0;
  92.         while(l<=r){
  93.             int m = (l+r)/2;
  94.             if(query(1, m, 1, n, 1)>=val){
  95.                 ans=m;
  96.                 r=m-1;
  97.             }else{
  98.                 l=m+1;
  99.             }
  100.  
  101.         }
  102.         cout<<ans-o.order_of_key(ans)<<" ";
  103.  
  104.         upd(ans, 0, 1, n, 1);
  105.         o.insert(ans);
  106.  
  107.  
  108.     }
  109.  
  110.  
  111.  
  112. }
  113.  
  114.  
  115.  
  116.  
  117. int32_t main()
  118. {
  119.  
  120.     ios_base::sync_with_stdio(0);
  121.     cin.tie(0);
  122.     int t = 1;
  123.  
  124.  
  125.     // cin >> t;
  126.     for(int i = 1; i <= t; i++)
  127.     {
  128.  
  129.         Solve();
  130.     }
  131.  
  132.  
  133.     return 0;
  134. }
  135.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
8 5
3 2 4 1 5 5 2 6
4 4 7 1 1
stdout
copy 
3 4 0 0 0
https://ideone.com/8F3qBx
language:
C++14 (clang 8.0)
created:
1 day 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!