#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; vector<long long> a(n), pref(n + 1); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end(), greater<long long>()); for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + a[i]; vector<tuple<long long, long long, int>> s; s.emplace_back(0, 0, n); while (m--) { long long d, b; cin >> d >> b; int left = 0, right = n; while (left < right) { int middle = (left + right) / 2; int s_left = 0, s_right = s.size() - 1; while (s_left < s_right) { int s_middle = (s_left + s_right + 1) / 2; if (get<2>(s[s_middle]) > middle) s_left = s_middle; else s_right = s_middle - 1; } long long h = (d - get<0>(s[s_left])) * a[middle] + get<1>(s[s_left]); if (h > b) left = middle + 1; else right = middle; } // cerr << "cutting first " << left << endl; long long ret = 0; int it = 0; while (it < left) { int next_it = min(left, get<2>(s.back())); ret += (next_it - it) * (get<1>(s.back()) - b) + (pref[next_it] - pref[it]) * (d - get<0>(s.back())); // cerr << "ret = " << ret << endl; if (get<2>(s.back()) <= left) s.pop_back(); it = next_it; } if (left > 0) s.emplace_back(d, b, left); cout << ret << endl; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; vector<long long> a(n), pref(n + 1); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end(), greater<long long>()); for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + a[i]; vector<tuple<long long, long long, int>> s; s.emplace_back(0, 0, n); while (m--) { long long d, b; cin >> d >> b; int left = 0, right = n; while (left < right) { int middle = (left + right) / 2; int s_left = 0, s_right = s.size() - 1; while (s_left < s_right) { int s_middle = (s_left + s_right + 1) / 2; if (get<2>(s[s_middle]) > middle) s_left = s_middle; else s_right = s_middle - 1; } long long h = (d - get<0>(s[s_left])) * a[middle] + get<1>(s[s_left]); if (h > b) left = middle + 1; else right = middle; } // cerr << "cutting first " << left << endl; long long ret = 0; int it = 0; while (it < left) { int next_it = min(left, get<2>(s.back())); ret += (next_it - it) * (get<1>(s.back()) - b) + (pref[next_it] - pref[it]) * (d - get<0>(s.back())); // cerr << "ret = " << ret << endl; if (get<2>(s.back()) <= left) s.pop_back(); it = next_it; } if (left > 0) s.emplace_back(d, b, left); cout << ret << endl; } } |