fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<ii, int> iii;
  8.  
  9. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  10. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  11. #define rep(i, n) for(int i=0; i<(n); ++i)
  12. #define red(i, n) for(int i=(n)-1; i>=0; --i)
  13. #define mp make_pair
  14. #define pb push_back
  15. #define fi first
  16. #define se second
  17. #define all(x) x.begin(), x.end()
  18. #define task "icebearat"
  19.  
  20. const int MOD = 1e9 + 7;
  21. const int inf = 1e9 + 27092008;
  22. const ll LLinf = 1e18 + 27092008;
  23. const int N = 2e5 + 5;
  24. int n, q, a[N];
  25. ll pref[N];
  26.  
  27. void solve() {
  28.     cin >> n >> q;
  29.     FOR(i, 1, n) cin >> a[i];
  30.     sort(a + 1, a + n + 1);
  31.     FOR(i, 1, n) pref[i] = pref[i - 1] + a[i];
  32.     while(q--) {
  33.         int k, m;
  34.         cin >> k >> m;
  35.  
  36.         int l = 0, r = m, res = 0;
  37.         while(l <= r) {
  38.             int mid = (l + r) >> 1;
  39.             if (a[mid] > k) {
  40.                 r = mid - 1;
  41.                 continue;
  42.             }
  43.  
  44.             if (a[n - m + mid] <= k) {
  45.                 l = mid + 1;
  46.                 res = mid;
  47.                 continue;
  48.             }
  49.  
  50.             int valLeft = a[mid];
  51.             int valRight = 2 * k - a[n - m + mid];
  52.             if (valLeft < valRight) res = mid, l = mid + 1;
  53.             else r = mid - 1; 
  54.         }  
  55.  
  56.         cout << pref[res] + 2LL * k * (m - res) - (pref[n] - pref[n - m + res]) << '\n';
  57.     } 
  58. }
  59.  
  60. signed main() {
  61.     ios_base::sync_with_stdio(0);
  62.     cin.tie(0); cout.tie(0);
  63.     if (fopen(task".inp", "r")){
  64.         freopen(task".inp", "r", stdin);
  65.         freopen(task".out", "w", stdout);
  66.     }
  67.     int tc = 1;
  68. //     cin >> tc;
  69.     while(tc--) solve();
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JWm11H
language:
C++14 (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!