fork(3) download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. ll t,n,q,a[100009],x,ans[100009];
  6. vector< pair<ll,ll> > qr;
  7.  
  8. int main()
  9. {
  10. cin>>t;
  11. while(t--)
  12. {
  13. qr.clear();
  14. cin>>n>>q;
  15. for(int i=1;i<n+1;i++)
  16. cin>>a[i];
  17. for(int i=0;i<q;i++)
  18. {
  19. cin>>x;
  20. qr.push_back(make_pair(x,i));
  21. }
  22. sort(a+1,a+n+1);
  23. sort(qr.begin(),qr.end());
  24. ll cur=0;
  25. ll prev=0,presum=0;
  26. for(int i=1;;i++)
  27. {
  28. ll fir = qr[cur].first;
  29. while(a[i] < fir && i<n+1)
  30. {
  31. presum += (fir-a[i]);
  32. i++;
  33. }
  34. i--;
  35. while(presum > prev)
  36. {
  37. prev++;
  38. presum -= (fir-a[prev]);
  39. }
  40. ans[qr[cur].second] = n-prev;
  41. if(cur == q-1)
  42. break;
  43. presum = presum + (i-prev)*(qr[cur+1].first - fir);
  44. cur++;
  45. }
  46. for(int i=0;i<q;i++)
  47. cout<<ans[i]<<"\n";
  48. }
  49. }
Success #stdin #stdout 0s 17616KB
stdin
Standard input is empty
stdout
Standard output is empty