#include<cstdio> #include<algorithm> #include<vector> using namespace std; struct cut { int pos; long long time; long long h; }; long long grow[500001]; long long pref[500001]; vector<cut> V; cut findh(int i) { int p = 0; int q = V.size()-1; while (p < q) { int s = (p+q+1)/2; if (V[s].pos <= i) { p = s; } else { q = s-1; } } return V[p]; } int binsearch(int p, int q, long long t, long long h) { while (p<q) { int s = (p+q)/2; cut lastcut = findh(s); if (lastcut.h + (t - lastcut.time) * grow[s] > h) { q = s; } else { p = s+1; } } return p; } int main() { int n; int m; scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) { scanf("%lld", &grow[i]); } sort(grow, grow+n); pref[0] = grow[0]; for (int i = 0; i < n; i++) { pref[i] = pref[i-1] + grow[i]; } cut temp; temp.pos = 0; temp.time = 0; temp.h = 0; V.push_back(temp); for (int i = 0; i < m; i++) { long long t; long long h; scanf("%lld%lld", &t, &h); int k = binsearch(0, n, t, h); long long res = 0; int q = n; while (V.size() > 0 && V[V.size()-1].pos >= k) { cut temp = V[V.size()-1]; V.pop_back(); res += (temp.h-h)*(q-temp.pos) + (t-temp.time)*((q > 0 ? pref[q-1] : 0) - (temp.pos > 0 ? pref[temp.pos-1] : 0)); q = temp.pos; } cut temp = V[V.size()-1]; res += (temp.h-h)*(q-k) + (t-temp.time)*((q > 0 ? pref[q-1] : 0) - (k > 0 ? pref[k-1] : 0)); printf("%lld\n", res); temp.h = h; temp.pos = k; temp.time = t; V.push_back(temp); } 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 | #include<cstdio> #include<algorithm> #include<vector> using namespace std; struct cut { int pos; long long time; long long h; }; long long grow[500001]; long long pref[500001]; vector<cut> V; cut findh(int i) { int p = 0; int q = V.size()-1; while (p < q) { int s = (p+q+1)/2; if (V[s].pos <= i) { p = s; } else { q = s-1; } } return V[p]; } int binsearch(int p, int q, long long t, long long h) { while (p<q) { int s = (p+q)/2; cut lastcut = findh(s); if (lastcut.h + (t - lastcut.time) * grow[s] > h) { q = s; } else { p = s+1; } } return p; } int main() { int n; int m; scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) { scanf("%lld", &grow[i]); } sort(grow, grow+n); pref[0] = grow[0]; for (int i = 0; i < n; i++) { pref[i] = pref[i-1] + grow[i]; } cut temp; temp.pos = 0; temp.time = 0; temp.h = 0; V.push_back(temp); for (int i = 0; i < m; i++) { long long t; long long h; scanf("%lld%lld", &t, &h); int k = binsearch(0, n, t, h); long long res = 0; int q = n; while (V.size() > 0 && V[V.size()-1].pos >= k) { cut temp = V[V.size()-1]; V.pop_back(); res += (temp.h-h)*(q-temp.pos) + (t-temp.time)*((q > 0 ? pref[q-1] : 0) - (temp.pos > 0 ? pref[temp.pos-1] : 0)); q = temp.pos; } cut temp = V[V.size()-1]; res += (temp.h-h)*(q-k) + (t-temp.time)*((q > 0 ? pref[q-1] : 0) - (k > 0 ? pref[k-1] : 0)); printf("%lld\n", res); temp.h = h; temp.pos = k; temp.time = t; V.push_back(temp); } return 0; } |