#include <cstdio> #include <utility> #include <algorithm> #include <vector> using namespace std; long long tree[1100000]; vector < pair < long long, long long> > stos; long long n, m, a[500001], treesize = 1, pom; long long d[500001], b[500001], suf[500002], pom2, h, t, wyn, pom3; long long query(int a) { long long va = a + treesize - 1, ret = 0; while (va != 0) { if (tree[va] > ret) ret = tree[va]; va /= 2; } return ret; } void ins(int a, int b) { long long va = a + treesize - 1; tree[va] = b; while (va != 0) { if (va % 2 == 0) tree[va+1] = b; va /= 2; } return; } long long binser() { long long l = 1, p = n, sr, ret = n+1, pom; while (l <= p) { sr = (l+p)/2; pom = query(sr); pom = (t-d[pom])*a[sr]+b[pom]; if (pom <= h) l = sr+1; else { p = sr-1; ret = sr; } } return ret; } int main() { scanf("%lld%lld", &n, &m); while(treesize < n) treesize *= 2; for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a+1, a + n + 1); for (int i = n; i >= 1; i--) suf[i] = a[i] + suf[i+1]; stos.push_back(make_pair(0,0)); for (int i = 1; i <= m; i++) { wyn = 0; scanf("%lld%lld", &d[i], &b[i]); t = d[i]; h = b[i]; pom = binser(); // printf("%d\n", pom); ins(pom, i); pom3 = n+1; while(stos[stos.size()-1].first >= pom) { wyn += (suf[stos[stos.size()-1].first] - suf[pom3])*(t-d[stos[stos.size()-1].second])-(pom3-stos[stos.size()-1].first)*(h-b[stos[stos.size()-1].second]); pom3 = stos[stos.size()-1].first; stos.pop_back(); } wyn += (suf[pom] - suf[pom3])*(t-d[stos[stos.size()-1].second])-(pom3-pom)*(h-b[stos[stos.size()-1].second]); stos.push_back(make_pair(pom,i)); printf("%lld\n", wyn); } 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 | #include <cstdio> #include <utility> #include <algorithm> #include <vector> using namespace std; long long tree[1100000]; vector < pair < long long, long long> > stos; long long n, m, a[500001], treesize = 1, pom; long long d[500001], b[500001], suf[500002], pom2, h, t, wyn, pom3; long long query(int a) { long long va = a + treesize - 1, ret = 0; while (va != 0) { if (tree[va] > ret) ret = tree[va]; va /= 2; } return ret; } void ins(int a, int b) { long long va = a + treesize - 1; tree[va] = b; while (va != 0) { if (va % 2 == 0) tree[va+1] = b; va /= 2; } return; } long long binser() { long long l = 1, p = n, sr, ret = n+1, pom; while (l <= p) { sr = (l+p)/2; pom = query(sr); pom = (t-d[pom])*a[sr]+b[pom]; if (pom <= h) l = sr+1; else { p = sr-1; ret = sr; } } return ret; } int main() { scanf("%lld%lld", &n, &m); while(treesize < n) treesize *= 2; for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a+1, a + n + 1); for (int i = n; i >= 1; i--) suf[i] = a[i] + suf[i+1]; stos.push_back(make_pair(0,0)); for (int i = 1; i <= m; i++) { wyn = 0; scanf("%lld%lld", &d[i], &b[i]); t = d[i]; h = b[i]; pom = binser(); // printf("%d\n", pom); ins(pom, i); pom3 = n+1; while(stos[stos.size()-1].first >= pom) { wyn += (suf[stos[stos.size()-1].first] - suf[pom3])*(t-d[stos[stos.size()-1].second])-(pom3-stos[stos.size()-1].first)*(h-b[stos[stos.size()-1].second]); pom3 = stos[stos.size()-1].first; stos.pop_back(); } wyn += (suf[pom] - suf[pom3])*(t-d[stos[stos.size()-1].second])-(pom3-pom)*(h-b[stos[stos.size()-1].second]); stos.push_back(make_pair(pom,i)); printf("%lld\n", wyn); } return 0; } |