#include <vector> #include <iostream> #include <sstream> #include <math.h> #include <sys/time.h> #include <cstdlib> #include <algorithm> #include <cassert> #include <cstring> #include <fstream> #include <set> #define FOR(i,a,b) for(__typeof(b) i=(a);i<(b);++i) #define REP(i,a) FOR(i,0,a) #define FOREACH(x,c) for(__typeof(c.begin()) x=c.begin();x != c.end(); x++) #define ALL(c) c.begin(),c.end() #define CLEAR(c) memset(c,0,sizeof(c)) #define SIZE(c) (int) ((c).size()) #define PB push_back #define MP make_pair #define X first #define Y second #define ULL unsigned long long #define LL long long #define LD long double #define II pair<int, int> #define DD pair<double, double> #define VC vector #define VI VC<int> #define VVI VC<VI> #define VD VC<double> #define VS VC<string> #define VII VC<II> #define VDD VC<DD> #define DB(a) cerr << #a << ": " << a << endl; using namespace std; template<class T> void print(VC < T > v) {cerr << "[";if (SIZE(v) != 0) cerr << v[0]; FOR(i, 1, SIZE(v)) cerr << "," << v[i]; cerr << "]\n";} template<class T> string i2s(T &x) { ostringstream o; o << x; return o.str(); } VS split(string &s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < SIZE(s)) all.PB(s.substr(p)); return all;} struct Cut{ LL d, h; int x,y; Cut(LL d, LL h, int x, int y) : d(d), h(h), x(x), y(y){} }; int main(int argc, char *argv[]){ int n,m; scanf("%d %d",&n,&m); VC<LL> v(n+1); REP(i,n) scanf("%lld",&(v[i])); v[n] = 0; sort(ALL(v)); VC<LL> revSum(n+2); revSum[n+1] = 0; for(int i=n; i>=0; i--) revSum[i] = revSum[i+1]+v[i]; VC<Cut> stack; stack.PB(Cut(0,0,0,0)); stack.PB(Cut(0,0,1,n)); LL d, h; REP(i,m){ scanf("%lld %lld",&d,&h); LL total = 0; for(;;){ Cut &c = stack.back(); if (c.h + (d-c.d)*v[c.y] <= h) break; if (c.h + (d-c.d)*v[c.x] > h){ total += (revSum[c.x]-revSum[c.y+1])*(d-c.d)+(c.y-c.x+1)*(c.h-h); stack.pop_back(); continue; } LL threshold = (h-c.h)/(d-c.d); int x = upper_bound(v.begin()+c.x,v.begin()+c.y+1,threshold) - v.begin(); total += (revSum[x]-revSum[c.y+1])*(d-c.d)+(c.y-x+1)*(c.h-h); c.y = x-1; break; } if (stack.back().y < n) stack.PB(Cut(d,h,stack.back().y+1,n)); printf("%lld\n",total); } 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 <vector> #include <iostream> #include <sstream> #include <math.h> #include <sys/time.h> #include <cstdlib> #include <algorithm> #include <cassert> #include <cstring> #include <fstream> #include <set> #define FOR(i,a,b) for(__typeof(b) i=(a);i<(b);++i) #define REP(i,a) FOR(i,0,a) #define FOREACH(x,c) for(__typeof(c.begin()) x=c.begin();x != c.end(); x++) #define ALL(c) c.begin(),c.end() #define CLEAR(c) memset(c,0,sizeof(c)) #define SIZE(c) (int) ((c).size()) #define PB push_back #define MP make_pair #define X first #define Y second #define ULL unsigned long long #define LL long long #define LD long double #define II pair<int, int> #define DD pair<double, double> #define VC vector #define VI VC<int> #define VVI VC<VI> #define VD VC<double> #define VS VC<string> #define VII VC<II> #define VDD VC<DD> #define DB(a) cerr << #a << ": " << a << endl; using namespace std; template<class T> void print(VC < T > v) {cerr << "[";if (SIZE(v) != 0) cerr << v[0]; FOR(i, 1, SIZE(v)) cerr << "," << v[i]; cerr << "]\n";} template<class T> string i2s(T &x) { ostringstream o; o << x; return o.str(); } VS split(string &s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < SIZE(s)) all.PB(s.substr(p)); return all;} struct Cut{ LL d, h; int x,y; Cut(LL d, LL h, int x, int y) : d(d), h(h), x(x), y(y){} }; int main(int argc, char *argv[]){ int n,m; scanf("%d %d",&n,&m); VC<LL> v(n+1); REP(i,n) scanf("%lld",&(v[i])); v[n] = 0; sort(ALL(v)); VC<LL> revSum(n+2); revSum[n+1] = 0; for(int i=n; i>=0; i--) revSum[i] = revSum[i+1]+v[i]; VC<Cut> stack; stack.PB(Cut(0,0,0,0)); stack.PB(Cut(0,0,1,n)); LL d, h; REP(i,m){ scanf("%lld %lld",&d,&h); LL total = 0; for(;;){ Cut &c = stack.back(); if (c.h + (d-c.d)*v[c.y] <= h) break; if (c.h + (d-c.d)*v[c.x] > h){ total += (revSum[c.x]-revSum[c.y+1])*(d-c.d)+(c.y-c.x+1)*(c.h-h); stack.pop_back(); continue; } LL threshold = (h-c.h)/(d-c.d); int x = upper_bound(v.begin()+c.x,v.begin()+c.y+1,threshold) - v.begin(); total += (revSum[x]-revSum[c.y+1])*(d-c.d)+(c.y-x+1)*(c.h-h); c.y = x-1; break; } if (stack.back().y < n) stack.PB(Cut(d,h,stack.back().y+1,n)); printf("%lld\n",total); } return 0; } |