fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define ll long long
  6. #define all(x) (x).begin(), (x).end()
  7. #define MASK(i) (1LL<<(i))
  8. #define BIT(i,n) (((n)>>(i)) & 1LL)
  9.  
  10. template <class X, class Y>
  11.     bool minimize(X& x, const Y& y)
  12.     {
  13.         if(x > y){
  14.             x = y;
  15.             return 1;
  16.         }
  17.         return 0;
  18.     }
  19.  
  20. template <class X, class Y>
  21.     bool maximize(X& x, const Y& y)
  22.     {
  23.         if(x < y){
  24.             x = y;
  25.             return 1;
  26.         }
  27.         return 0;
  28.     }
  29.  
  30. const int N = 1e5 + 5;
  31.  
  32. int n, q, a[N], k, m;
  33. ll pref[N], ans;
  34.  
  35. int findpos(int k)
  36. {
  37.     int l = 1, r = n, mid, res = n;
  38.     while(l <= r){
  39.         mid = l + r >> 1;
  40.         if(a[mid] <= k) l = mid + 1, res = mid;
  41.         else r = mid - 1;
  42.     }
  43.     return res;
  44. }
  45.  
  46. ll calc(const int &posI)
  47. {
  48.     int posJ = m - posI;
  49.     return pref[posI] + (posJ * 2LL * k - (pref[n] - pref[n - posJ]));
  50. }
  51.  
  52. void process()
  53. {
  54.     cin >> n >> q;
  55.     for(int i = 1; i <= n; ++i) cin >> a[i];
  56.     sort(a + 1, a + 1 + n);
  57.  
  58.     for(int i = 1; i <= n; ++i){
  59.         pref[i] = pref[i - 1] + a[i];
  60.     }
  61.  
  62.     while(q--){
  63.         cin >> k >> m;
  64.         int t = findpos(k);
  65.         int l = 0, r = min(t, m), mid, posI = r;
  66.         while(l <= r){
  67.             mid = l + r >> 1;
  68.             if(a[mid] - (2 * k - a[n - (m - mid) + 1]) >= 0) r = mid - 1, posI = mid;
  69.             else l = mid + 1;
  70.         }
  71.  
  72.         ans = calc(posI);
  73.         if(posI > 0) minimize(ans, calc(posI - 1));
  74.         cout << ans << "\n";
  75.     }
  76. }
  77.  
  78. int main()
  79. {
  80.     ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  81.     #define file "thieufilethinguhetcuu"
  82.     if(fopen(file".inp","r")){
  83.         freopen(file".inp","r",stdin);
  84.         freopen(file".out","w",stdout);
  85.     }
  86.     int _ = 1;
  87. //    cin >> _;
  88.     while(_--){
  89.         process();
  90.     }
  91.     return 0;
  92. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ccOmTN
language:
C++14 (gcc 8.3)
created:
3 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!