#include <iostream> #include <vector> #include <algorithm> using ll = long long int; struct interval { int begin, end; ll cut_day; ll above; }; int interval_search(std::vector<interval> const &_intervals, int _i_size, int _idx) { int low = 0, high = _i_size - 1; while (low < high) { int mid = low + (high - low) / 2; if (_intervals[mid].end < _idx) { low = mid + 1; } else { high = mid; } } return low; } int value_search(std::vector<int> const &_a, ll _d, ll _b, std::vector<interval> const &_intervals, int _i_size) { int low = 0, high = _a.size() - 1; while (low < high) { int mid = low + (high - low) / 2; int i_idx = interval_search(_intervals, _i_size, mid); ll val = static_cast<ll>(_a[mid]) * (_d - _intervals[i_idx].cut_day) + _intervals[i_idx].above; if (!(_b < val)) { low = mid + 1; } else { high = mid; } } return low; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> a(n + 1); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } a[n] = 1000001; std::sort(a.begin(), a.end()); std::vector<ll> sums(n + 1); sums[0] = 0; for (int i = 0; i < n; ++i) { sums[i + 1] = sums[i] + a[i]; } int i_end = 0; std::vector<interval> intervals(n); intervals[i_end++] = { 0, n - 1, 0, 0 }; ll d, b; for (int i = 0; i < m; ++i) { std::cin >> d >> b; int cut_idx = value_search(a, d, b, intervals, i_end); if (cut_idx == n) { std::cout << 0 << std::endl; continue; } int i_idx = interval_search(intervals, i_end, cut_idx); ll ans = 0; ans += (sums[intervals[i_idx].end + 1] - sums[cut_idx]) * (d - intervals[i_idx].cut_day); ans -= (intervals[i_idx].end - cut_idx + 1) * (b - intervals[i_idx].above); for (int j = i_idx + 1; j < i_end; ++j) { ans += (sums[intervals[j].end + 1] - sums[intervals[j].begin]) * (d - intervals[j].cut_day); ans -= (intervals[j].end - intervals[j].begin + 1) * (b - intervals[j].above); } if (intervals[i_idx].begin == cut_idx) { // correct interval intervals[i_idx].end = n - 1; intervals[i_idx].cut_day = d; intervals[i_idx].above = b; } else { // split interval intervals[i_idx++].end = cut_idx - 1; intervals[i_idx] = { cut_idx, n - 1, d, b }; } i_end = i_idx + 1; std::cout << ans << std::endl; } return 0; }
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <iostream> #include <vector> #include <algorithm> using ll = long long int; struct interval { int begin, end; ll cut_day; ll above; }; int interval_search(std::vector<interval> const &_intervals, int _i_size, int _idx) { int low = 0, high = _i_size - 1; while (low < high) { int mid = low + (high - low) / 2; if (_intervals[mid].end < _idx) { low = mid + 1; } else { high = mid; } } return low; } int value_search(std::vector<int> const &_a, ll _d, ll _b, std::vector<interval> const &_intervals, int _i_size) { int low = 0, high = _a.size() - 1; while (low < high) { int mid = low + (high - low) / 2; int i_idx = interval_search(_intervals, _i_size, mid); ll val = static_cast<ll>(_a[mid]) * (_d - _intervals[i_idx].cut_day) + _intervals[i_idx].above; if (!(_b < val)) { low = mid + 1; } else { high = mid; } } return low; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> a(n + 1); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } a[n] = 1000001; std::sort(a.begin(), a.end()); std::vector<ll> sums(n + 1); sums[0] = 0; for (int i = 0; i < n; ++i) { sums[i + 1] = sums[i] + a[i]; } int i_end = 0; std::vector<interval> intervals(n); intervals[i_end++] = { 0, n - 1, 0, 0 }; ll d, b; for (int i = 0; i < m; ++i) { std::cin >> d >> b; int cut_idx = value_search(a, d, b, intervals, i_end); if (cut_idx == n) { std::cout << 0 << std::endl; continue; } int i_idx = interval_search(intervals, i_end, cut_idx); ll ans = 0; ans += (sums[intervals[i_idx].end + 1] - sums[cut_idx]) * (d - intervals[i_idx].cut_day); ans -= (intervals[i_idx].end - cut_idx + 1) * (b - intervals[i_idx].above); for (int j = i_idx + 1; j < i_end; ++j) { ans += (sums[intervals[j].end + 1] - sums[intervals[j].begin]) * (d - intervals[j].cut_day); ans -= (intervals[j].end - intervals[j].begin + 1) * (b - intervals[j].above); } if (intervals[i_idx].begin == cut_idx) { // correct interval intervals[i_idx].end = n - 1; intervals[i_idx].cut_day = d; intervals[i_idx].above = b; } else { // split interval intervals[i_idx++].end = cut_idx - 1; intervals[i_idx] = { cut_idx, n - 1, d, b }; } i_end = i_idx + 1; std::cout << ans << std::endl; } return 0; } |