Advertisement
Guest User

Untitled

a guest
May 22nd, 2017
43
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll MX = (1<<21);
  5. vector < ll > bucket[64];
  6. vector < ll > Queries;
  7. ll ans[MX] , arr[MX];
  8. void merge_(vector < ll > &a , vector < ll > &b){
  9.     vector < ll > ret;
  10.     ll it1 = 0 , it2 = 0;
  11.     while(it1 < a.size() && it2 < b.size())
  12.         if(a[it1] < b[it2])
  13.             ret.push_back(a[it1++]);
  14.         else ret.push_back(b[it2++]);
  15.     while(it1 < a.size()) ret.push_back(a[it1++]);
  16.     while(it2 < b.size()) ret.push_back(b[it2++]);
  17.     a.swap(ret);
  18.     b.clear();
  19. }
  20. int main(){
  21.     ll n , QN;
  22.     scanf("%lld %lld",&n,&QN);
  23.     for(ll j = 1 ; j <= n ; j++) scanf("%lld",&arr[j]);
  24.     sort(arr+1 , arr+1+n);
  25.     for(ll j = 1 ; j <= n ; j++){
  26.         for(ll i = 62 ; i >= 0 ; i--){
  27.             if( (arr[j] & (1ll<<i)) ){
  28.                 bucket[i].push_back(arr[j]);
  29.                 break;
  30.             }
  31.         }
  32.     }
  33.     for(ll j = 1 ; j <= QN ; j++){
  34.         ll x;
  35.         scanf("%lld",&x);
  36.         Queries.push_back(x);
  37.     }
  38.     ll it = 0 , last = 0;
  39.     for(ll bit = 62 ; bit >= 0 ; bit--){
  40.         ll sz = bucket[bit].size();
  41.         while(it < QN && Queries[it] - last <= sz){
  42.             printf("%lld\n",bucket[bit][sz - Queries[it] + last]);
  43.             ++it;
  44.         }
  45.         for(auto &pp : bucket[bit]) pp >>= 1;
  46.         last += bucket[bit].size();
  47.         if(bit == 0) break;
  48.         merge_(bucket[bit-1] , bucket[bit]);
  49.     }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement