#include<cstdio> #include<algorithm> #include<stack> #include<cassert> #define FOR(i, b, n) for ( int (i) = b; (i) < (n); (i)++) #define FORR(i, b, n) for ( (i) = b; (i) < (n); (i)++) #define REP(i, n) for ( int (i) = 0; (i) < (n); (i)++) #define SC(n) scanf("%d", &(n)) #define SC2(n, m) scanf("%d%d", &(n), &(m)) #define SCLL(n) scanf("%lld", &(n)) #define PRT(n) printf("%d ", (n)) #define PRTLL(n) printf("%lld ", (n)) #define NXL printf("\n") typedef long long LL;// typedef unsigned long long ULL; using namespace std; #define st first #define nd second #define pb push_back const int MANY = 5e5+9; int a[MANY]; LL pref[MANY];//, d[MANY], b[MANY]; int n, m; const LL INF = (LL)2e18; struct cut { LL d, b, grass; int start; cut(LL d, LL b, int st, LL gr) : d(d), b(b), start(st), grass(gr) {} }; stack<cut> s; bool try_remove(LL d, LL b, LL& res, int& laststart) { const cut& t = s.top(); if(b >= t.b + (d - t.d)*a[t.start]) return false; s.pop(); assert(!s.empty()); res += (t.b - b)*(laststart - t.start) + (d - t.d) * (pref[laststart] - pref[t.start]); laststart = t.start; return true; } int bins(const cut& t, LL d, LL b) { int p = t.start, q = n; while(p < q) { int mid = (p+q)/2; if(b > (t.b == -INF ? 0 : t.b) + (d-t.d)*a[mid]) p = mid+1; else q = mid; } return p; } int main() { while(!s.empty()) s.pop(); SC2(n, m); REP(i, n) SC(a[i]); sort(a, a+n); LL sum = 0; REP(i, n) { pref[i] = sum; sum += a[i]; } pref[n] = sum; a[n] = 100000000; //LL s.push(cut(0, -INF, 0, 0)); //0 or -1? LL printed = 0; REP(i, m) { LL d, b; long long dd, bb; scanf("%lld%lld", &dd, &bb); d = dd; b = bb; LL res = 0; int laststart = n; while(try_remove(d, b, res, laststart)) ; const cut& t = s.top(); int start = bins(t, d, b); res += ((t.b == -INF ? 0 : t.b) - b)*(laststart - start) + (d - t.d) * (pref[laststart] - pref[start]); s.push(cut(d, b, start, res)); //LL res = d*sum - grass; //long long to_print = res - printed; //PRTLL((long long)d); //PRTLL((long long)sum); //PRTLL((long long)grass); //PRTLL((long long)(d*sum)); PRTLL(res); NXL; } 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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include<cstdio> #include<algorithm> #include<stack> #include<cassert> #define FOR(i, b, n) for ( int (i) = b; (i) < (n); (i)++) #define FORR(i, b, n) for ( (i) = b; (i) < (n); (i)++) #define REP(i, n) for ( int (i) = 0; (i) < (n); (i)++) #define SC(n) scanf("%d", &(n)) #define SC2(n, m) scanf("%d%d", &(n), &(m)) #define SCLL(n) scanf("%lld", &(n)) #define PRT(n) printf("%d ", (n)) #define PRTLL(n) printf("%lld ", (n)) #define NXL printf("\n") typedef long long LL;// typedef unsigned long long ULL; using namespace std; #define st first #define nd second #define pb push_back const int MANY = 5e5+9; int a[MANY]; LL pref[MANY];//, d[MANY], b[MANY]; int n, m; const LL INF = (LL)2e18; struct cut { LL d, b, grass; int start; cut(LL d, LL b, int st, LL gr) : d(d), b(b), start(st), grass(gr) {} }; stack<cut> s; bool try_remove(LL d, LL b, LL& res, int& laststart) { const cut& t = s.top(); if(b >= t.b + (d - t.d)*a[t.start]) return false; s.pop(); assert(!s.empty()); res += (t.b - b)*(laststart - t.start) + (d - t.d) * (pref[laststart] - pref[t.start]); laststart = t.start; return true; } int bins(const cut& t, LL d, LL b) { int p = t.start, q = n; while(p < q) { int mid = (p+q)/2; if(b > (t.b == -INF ? 0 : t.b) + (d-t.d)*a[mid]) p = mid+1; else q = mid; } return p; } int main() { while(!s.empty()) s.pop(); SC2(n, m); REP(i, n) SC(a[i]); sort(a, a+n); LL sum = 0; REP(i, n) { pref[i] = sum; sum += a[i]; } pref[n] = sum; a[n] = 100000000; //LL s.push(cut(0, -INF, 0, 0)); //0 or -1? LL printed = 0; REP(i, m) { LL d, b; long long dd, bb; scanf("%lld%lld", &dd, &bb); d = dd; b = bb; LL res = 0; int laststart = n; while(try_remove(d, b, res, laststart)) ; const cut& t = s.top(); int start = bins(t, d, b); res += ((t.b == -INF ? 0 : t.b) - b)*(laststart - start) + (d - t.d) * (pref[laststart] - pref[start]); s.push(cut(d, b, start, res)); //LL res = d*sum - grass; //long long to_print = res - printed; //PRTLL((long long)d); //PRTLL((long long)sum); //PRTLL((long long)grass); //PRTLL((long long)(d*sum)); PRTLL(res); NXL; } return 0; } |