#define NDEBUG #include <cstdio> #include <cstdlib> #include <algorithm> #include <cassert> using namespace std; using ll = long long; #define MAXN 500001 ll A[MAXN], S[MAXN]; ll qAI[MAXN], qD[MAXN], qB[MAXN]; ll qLen = 1; ll GetQI(ll aI); void Harv(ll aI, ll d, ll b); ll n, m; int main() { scanf("%lld%lld", &n, &m); for(int i = 0; i < n; ++i) scanf("%lld", &A[i]); sort(A, A+n); S[0] = 0; for(int i = 1; i <= n; ++i) S[i] = S[i-1] + A[i-1]; for(int i = 0; i < m; ++i) { ll d, b; scanf("%lld%lld", &d, &b); auto up = upper_bound(A, A+n, b, [d](ll _b, ll _a) { auto qI = GetQI(_a); auto h = qB[qI] + (d - qD[qI])*_a; return _b < h; }); auto aI = up-A; if(aI == n) puts("0"); else Harv(aI, d, b); } return 0; } ll GetQI(ll a) { assert(a > 0); auto low = lower_bound(qAI, qAI + qLen, a, [](ll aI, ll _a) { assert(aI < n); return A[aI] < _a; }); auto qI = low - qAI; if(qI == qLen || A[*low] > a) --qI; assert(qI >= 0); assert(qI < qLen); return qI; } ll HarvRange(ll begI, ll endI, ll dB, ll dD); void Harv(ll aI, ll d, ll b) { assert(aI >= 0); ll harvResult = 0; ll currEndHarvI = n; while(qAI[qLen - 1] >= aI && qLen > 0) { auto lastQI = qLen - 1; harvResult += HarvRange(qAI[lastQI], currEndHarvI, b - qB[lastQI], d - qD[lastQI]); currEndHarvI = qAI[lastQI]; --qLen; } if(aI < currEndHarvI) { assert(aI > 0); auto lastQI = qLen - 1; harvResult += HarvRange(aI, currEndHarvI, b - qB[lastQI], d - qD[lastQI]); } qAI[qLen] = aI; qD[qLen] = d; qB[qLen++] = b; printf("%lld\n", harvResult); } ll HarvRange(ll begI, ll endI, ll dB, ll dD) { assert(begI < endI); auto count = endI - begI; return dD*(S[endI]-S[begI]) - count*dB; }
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 | #define NDEBUG #include <cstdio> #include <cstdlib> #include <algorithm> #include <cassert> using namespace std; using ll = long long; #define MAXN 500001 ll A[MAXN], S[MAXN]; ll qAI[MAXN], qD[MAXN], qB[MAXN]; ll qLen = 1; ll GetQI(ll aI); void Harv(ll aI, ll d, ll b); ll n, m; int main() { scanf("%lld%lld", &n, &m); for(int i = 0; i < n; ++i) scanf("%lld", &A[i]); sort(A, A+n); S[0] = 0; for(int i = 1; i <= n; ++i) S[i] = S[i-1] + A[i-1]; for(int i = 0; i < m; ++i) { ll d, b; scanf("%lld%lld", &d, &b); auto up = upper_bound(A, A+n, b, [d](ll _b, ll _a) { auto qI = GetQI(_a); auto h = qB[qI] + (d - qD[qI])*_a; return _b < h; }); auto aI = up-A; if(aI == n) puts("0"); else Harv(aI, d, b); } return 0; } ll GetQI(ll a) { assert(a > 0); auto low = lower_bound(qAI, qAI + qLen, a, [](ll aI, ll _a) { assert(aI < n); return A[aI] < _a; }); auto qI = low - qAI; if(qI == qLen || A[*low] > a) --qI; assert(qI >= 0); assert(qI < qLen); return qI; } ll HarvRange(ll begI, ll endI, ll dB, ll dD); void Harv(ll aI, ll d, ll b) { assert(aI >= 0); ll harvResult = 0; ll currEndHarvI = n; while(qAI[qLen - 1] >= aI && qLen > 0) { auto lastQI = qLen - 1; harvResult += HarvRange(qAI[lastQI], currEndHarvI, b - qB[lastQI], d - qD[lastQI]); currEndHarvI = qAI[lastQI]; --qLen; } if(aI < currEndHarvI) { assert(aI > 0); auto lastQI = qLen - 1; harvResult += HarvRange(aI, currEndHarvI, b - qB[lastQI], d - qD[lastQI]); } qAI[qLen] = aI; qD[qLen] = d; qB[qLen++] = b; printf("%lld\n", harvResult); } ll HarvRange(ll begI, ll endI, ll dB, ll dD) { assert(begI < endI); auto count = endI - begI; return dD*(S[endI]-S[begI]) - count*dB; } |