fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #include  "../debug.cpp"
  6. #else
  7. #define debug(...)
  8. #define debugArr(...)
  9. #endif
  10.  
  11. #define all(x) begin(x), end(x)
  12. #define sz(x) (int)(x).size()
  13. #define ff first
  14. #define ss second
  15. #define pb push_back
  16. #define BIG 998244353
  17. #define MOD 1000000007
  18. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  19. typedef long long ll;
  20. typedef pair<ll, ll> pii;
  21. typedef vector<ll> vi;
  22. typedef vector<pii> vpii;
  23. typedef vector<vi> vvi;
  24.  
  25. void solve() {
  26.     int n,m;
  27.     cin >> n >> m;
  28.  
  29.     vi ast(n);
  30.     vpii str(m);
  31.     for (int i = 0; i < n; i++)
  32.         cin >> ast[i];
  33.     for (int i = 0; i < m; i++) {
  34.         cin >> str[i].ff;
  35.         str[i].ss = i;
  36.     }
  37.  
  38.     sort(all(ast));
  39.     sort(all(str));
  40.     ll initStr = ast[0]+1, curStr = ast[0]+1;
  41.     // x -> 2x - 2y1 -> 4x - 4y1 - 2y2 -> 8x - 8y1 - 4y2 - 2y3
  42.     // x + 1 -> 2x - 2y1 + 2 -> 4x - 4y1 - 2y2 + 4
  43.  
  44.     int j = 0;
  45.     vi ans(m);
  46.     for (int i = 0; i < n && j < m; i++) {
  47.         if (curStr <= ast[i]) {
  48.             ll diff = ast[i]+1-curStr;
  49.             int pow = min(i,32);
  50.             ll cnt = (diff+((1ll<<pow)-1))/(1ll<<pow);
  51.             initStr += cnt;
  52.             curStr += cnt*(1ll<<pow);
  53.         } 
  54.  
  55.         debug(initStr,curStr);
  56.         while (j < m && str[j].ff < initStr) {
  57.             ans[str[j].ss] = i;
  58.             j++;
  59.         }
  60.  
  61.         curStr = 2ll*(curStr-ast[i]);
  62.     }
  63.  
  64.     while (j < m) {
  65.         ans[str[j].ss] = n;
  66.         j++;
  67.     }
  68.  
  69.     for (auto &x: ans) cout << x << " ";
  70.     cout << "\n";
  71. }
  72.  
  73. int main() {
  74.     auto start = chrono::high_resolution_clock::now();
  75.     fast_io;
  76.     int t;
  77.     cin >> t;
  78.  
  79.     while (t--) {
  80.         solve();
  81.     }
  82.  
  83.     #ifdef LOCAL
  84.         auto end = chrono::high_resolution_clock::now();
  85.         chrono::duration<double> duration = end - start;
  86.         cerr << "Execution time: " << duration.count() << " seconds" << endl;
  87.     #endif
  88. }
  89.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
1
3 3
1 2 3
1 2 4
stdout
copy 
0 1 3
https://ideone.com/WsISCh
language:
C++ (gcc 8.3)
created:
2 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!