AJ00567

Untitled

Dec 19th, 2024
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define int long long
  5. #define fo(i,n) for(int i = 0; i < n; i++)
  6. #define foll(i,n) for(ll i = 0; i < n; i++)
  7. int inf = 1e9+7,t=1,n,l,r,k,m,ans,temp,cur,sum,l1,r1,l2,r2,cnt,maxm,sto,defsolve,last;
  8. string s;
  9. int a[300005],b[300005],canbesolvedby[300001];
  10. vector<int> v,u;
  11. signed main()
  12. {
  13.     ios_base::sync_with_stdio(false);
  14.     cin.tie(0);
  15.     cout.tie(0);
  16.     cin >> t;
  17.    // cout << "u0 " << flush;
  18.     while(t--){
  19.         cin >> n >> m;
  20.         fo(i,n){
  21.             cin >> a[i];
  22.         }
  23.         fo(i,m){
  24.             cin >> b[i];
  25.         }
  26.         b[m] = inf;
  27.        /* if (n==1){
  28.             ans = 0;
  29.             for (int i = 1; i <= m; i++){
  30.                 cout << (m/i) << " ";
  31.             }
  32.             cout << "\n";
  33.             continue;
  34.         }*/
  35.         sort(b,b+m+1);
  36.         v.clear();
  37.         fo(i,m+1){
  38.             v.push_back(b[i]);
  39.         }
  40.        // b.push_back(inf);
  41.         /*itr = a.begin();
  42.         itr++;
  43.         sort(itr, a.end());*/
  44.         defsolve = upper_bound(v.begin(),v.end(),a[0])-v.begin();
  45.         v.pop_back();
  46.         sort(a,a+n);
  47.         u.clear();
  48.         fo(i,n){
  49.             u.push_back(a[i]);
  50.         }
  51.        // u.push_back(inf);
  52.         //cout << "\n";
  53.         fo (i,m){
  54.             if (b[i] > a[n-1]){
  55.                 canbesolvedby[i] = 0;
  56.                 continue;
  57.             }
  58.             canbesolvedby[i] = n-(lower_bound(u.begin(),u.end(),b[i])-u.begin());
  59.            // cout << b[i] << " " << canbesolvedby[i] << "\n" << flush;
  60.         }
  61.         for (int i = 1; i <= m; i++){
  62.             ans = (defsolve/i);
  63.             l = m;
  64.            // cout << ans << "a ";
  65.             if (defsolve%i != 0 && m != defsolve){
  66.                 ans += (canbesolvedby[l-i+(defsolve%i)])+1;
  67.                 l = l-i+(defsolve%i);
  68.             }
  69.             cnt = ((defsolve+i-1)/i);
  70.           //  cout << ans << " " << cnt << "b ";
  71.             //cout << cnt << " " << flush;
  72.             while (cnt < (m/i)){
  73.                 ans += (canbesolvedby[l-i])+1;
  74.                 l = l-i;
  75.                 cnt++;
  76.               //  cout << ans << "c ";
  77.             }
  78.             cout << ans << " ";
  79.         }
  80.         cout << "\n";
  81.     }
  82.     return 0;  
  83. }
Advertisement
Add Comment
Please, Sign In to add comment