fork download
copy 
  1. #include <algorithm>
  2. #include <bits/stdc++.h>
  3. #define int long long
  4. #define el '\n'
  5. #define oo LLONG_MAX >> 2
  6. #define all(x) x.begin(), x.end()
  7. #define allr(x) x.rbegin(), x.rend()
  8. #define pb push_back
  9. #define pep_Guardiola                                                          \
  10.   ios::sync_with_stdio(0);                                                     \
  11.   cin.tie(0);                                                                  \
  12.   cout.tie(0);
  13. using namespace std;
  14.  
  15. signed main() {
  16.   pep_Guardiola int t;
  17.   cin >> t;
  18.   while (t--) {
  19.     int n, q;
  20.     cin >> n >> q;
  21.     vector<int> a(n);
  22.     for (auto &i : a)
  23.       cin >> i;
  24.     sort(all(a));
  25.     vector<int> prefix(n);
  26.     prefix[0] = a[0];
  27.     for (int i = 1; i < n; i++)
  28.       prefix[i] = prefix[i - 1] + a[i];
  29.     auto calc = [&](int l, int r) -> int {
  30.       return prefix[r] - (l == 0 ? 0 : prefix[l - 1]);
  31.     };
  32.     auto go = [&](int k) -> int {
  33.       auto idx = lower_bound(all(a), k) - a.begin();
  34.       idx--;
  35.       int l = 0, r = idx, ans = idx + 1;
  36.       while (l <= r) {
  37.         int mid = (r + l) >> 1;
  38.         if (k * (idx - mid + 1) - calc(mid, idx) <= mid)
  39.           r = mid - 1, ans = mid;
  40.         else
  41.           l = mid + 1;
  42.       }
  43.       return n - ans;
  44.     };
  45.     while (q--) {
  46.       int k;
  47.       cin >> k;
  48.       cout << go(k) << el;
  49.     }
  50.   }
  51. }
  52.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
2
5 2
21 9 5 8 10
10
15
5 1
1 2 3 4 5
100
stdout
copy 
3
1
0
https://ideone.com/3wwBgB
language:
C++ (gcc 8.3)
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!