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 #include using namespace std; typedef long long int LL; struct trip{ LL day; LL element; LL high; void make_trip(LL a, LL b, LL c){ day = a; element = b; high = c; } }; #define el element #define PLL pair #define st first #define nd second #define mp make_pair #define PII pair #define mt make_trip const int mxn = 500007; const LL INF = 1000000000005LL; LL t[mxn]; LL suf[mxn]; LL add(LL from, LL to, LL sh, LL eh, LL sd, LL ed){ if(to < from) return 0LL; return ((to-from+1)*(sh-eh))+((suf[from] - suf[to+1])*(ed-sd)); } LL BS(LL from, LL to, LL sh, LL eh, LL sd, LL ed){ while(from < to){ LL sred = (from + to)/2LL; if(sh + (ed - sd)*t[sred] <= eh) from = sred+1; else to = sred; } return from; } int main() { LL n, m; scanf("%lld %lld", &n, &m); for(int i=1; i<=n; ++i) scanf("%lld", &t[i]); t[n+1] = INF; sort(t+1, t+n+1); for(int i=n; i>=0; --i) suf[i] = suf[i+1] + t[i]; deque Q; trip X; X.mt(0LL, 0LL, 0LL); Q.push_back(X); while(m--){ LL day, high; scanf("%lld %lld", &day, &high); trip k = Q.back(); trip last; last.mt(day, n+1, high); LL result = 0LL; while((day - k.day)*t[k.el] + k.high > high){ Q.pop_back(); result+= add(k.el, last.el-1, k.high, high, k.day, day); last = k; k=Q.back(); } LL where = BS(k.el, last.el, k.high, high, k.day, day); result+= add(where, last.el-1, k.high, high, k.day, day); printf("%lld\n", result); X.mt(day, where, high); Q.push_back(X); } return 0; }