#include <iostream> #include <algorithm> #include <stack> using namespace std; struct koszenie { int s; long long h, d; koszenie(int s, long long h, long long d) { this->s = s; this->h = h; this->d = d; } }; stack<koszenie> S; int n, m, T[500001]; long long suff[500001]; int bin_search(int a, int b, long long d, long long x) { while (a != b) { int c = (a + b) / 2; if (T[c] * d > x) b = c; else a = c + 1; } return a; } int main() { ios_base::sync_with_stdio(0); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> T[i]; } sort(T, T + n); suff[n] = 0; for (int i = n - 1; i >= 0; i--) { suff[i] = suff[i + 1] + T[i]; } S.push(koszenie(0, 0, 0)); for (int i = 0; i < m; i++) { long long d, b, r=0; int ns = n; cin >> d >> b; while ( !S.empty() && T[S.top().s] * (d - S.top().d) + S.top().h > b ) { // scinamy calosc r += (suff[S.top().s] - suff[ns]) * (d - S.top().d) + (S.top().h - b) * (ns - S.top().s); ns = S.top().s; S.pop(); } if (!S.empty() && T[ns - 1] * (d - S.top().d) + S.top().h > b) { // kawalek kolejnego przedzialu trza sciac int s = bin_search(S.top().s, ns - 1, d - S.top().d, b - S.top().h); r += (suff[s] - suff[ns]) * (d - S.top().d) + (S.top().h - b) * (ns - s); ns = s; } if (r > 0) { S.push(koszenie(ns, b, d)); } cout << r << 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 | #include <iostream> #include <algorithm> #include <stack> using namespace std; struct koszenie { int s; long long h, d; koszenie(int s, long long h, long long d) { this->s = s; this->h = h; this->d = d; } }; stack<koszenie> S; int n, m, T[500001]; long long suff[500001]; int bin_search(int a, int b, long long d, long long x) { while (a != b) { int c = (a + b) / 2; if (T[c] * d > x) b = c; else a = c + 1; } return a; } int main() { ios_base::sync_with_stdio(0); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> T[i]; } sort(T, T + n); suff[n] = 0; for (int i = n - 1; i >= 0; i--) { suff[i] = suff[i + 1] + T[i]; } S.push(koszenie(0, 0, 0)); for (int i = 0; i < m; i++) { long long d, b, r=0; int ns = n; cin >> d >> b; while ( !S.empty() && T[S.top().s] * (d - S.top().d) + S.top().h > b ) { // scinamy calosc r += (suff[S.top().s] - suff[ns]) * (d - S.top().d) + (S.top().h - b) * (ns - S.top().s); ns = S.top().s; S.pop(); } if (!S.empty() && T[ns - 1] * (d - S.top().d) + S.top().h > b) { // kawalek kolejnego przedzialu trza sciac int s = bin_search(S.top().s, ns - 1, d - S.top().d, b - S.top().h); r += (suff[s] - suff[ns]) * (d - S.top().d) + (S.top().h - b) * (ns - s); ns = s; } if (r > 0) { S.push(koszenie(ns, b, d)); } cout << r << endl; } return 0; } |