#include <iostream> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <cmath> #include <cassert> #include <cstring> #include <ext/numeric> using namespace std ; using namespace __gnu_cxx ; typedef long long LL ; typedef pair<int,int> PII ; typedef vector<int> VI ; const int INF = 1e9+100 ; const LL INFLL = (LL)INF * (LL)INF ; #define REP(i,n) for(i=0;i<(n);++i) #define ALL(c) c.begin(),c.end() #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define CLEAR(t) memset(t,0,sizeof(t)) #define PB push_back #define MP make_pair #define FI first #define SE second template<class T1,class T2> ostream& operator<<(ostream &s, const pair<T1,T2> &x) { s<< "(" << x.FI << "," << x.SE << ")"; return s;} template<class T> ostream& operator<<(ostream &s, const vector<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T> ostream& operator<<(ostream &s, const set<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T1,class T2> ostream& operator<<(ostream &s, const map<T1, T2> &t) { FOREACH(it, t) s << *it << " " ; return s ; } /////////////////////////////////////////// const int MAXX = 1000100 ; int counter[MAXX+1] ; LL sum[MAXX+1] ; struct segment { static LL addA ; LL a_, b ; int x, y ; segment(LL aa, LL bb, int xx, int yy) : a_(aa), b(bb), x(xx), y(yy) {} LL getVal(int p) const { //assert(x<=p && p<=y) ; return (a_+addA)*p + b ; } LL getLastVal() const { return getVal(y) ; } LL getFirstVal() const { return getVal(x) ; } int getFirstGreater(LL h) const { //assert(h<=getLastVal()) ; LL a = a_+addA ; //assert(a>0) ; //assert(h-b>=0) ; int ret = ((h-b)+(a-1))/a ; //assert(x<ret && ret<=y) ; return ret ; } LL cut(LL h, int p=-INF) const { //assert(p<=y) ; p = max(p, x) ; return (a_+addA)*(sum[y]-sum[p-1]) + (b-h)*(counter[y]-counter[p-1]) ; } } ; LL segment::addA=0 ; int main() { ios_base::sync_with_stdio(0) ; int n, m, i, x, MAXX=0 ; // przyslania cin >> n >> m ; REP(i,n) { cin >> x ; counter[x]++ ; MAXX = max(MAXX, x) ; } for(i=1 ; i<=MAXX ; i++) { sum[i] = sum[i-1] + (LL)i*counter[i] ; counter[i] += counter[i-1] ; } stack<segment> S ; S.push(segment(0,0, 1,MAXX)) ; LL d, h, prev_d=0 ; while(m--) { LL d, h ; cin >> d >> h ; segment::addA += d-prev_d ; prev_d = d ; if(S.top().getLastVal()<h) cout << 0 << endl ; else { LL ret = 0 ; while(!S.empty() && h<=S.top().getFirstVal()) { ret += S.top().cut(h) ; S.pop() ; } if(!S.empty() && h<=S.top().getLastVal()) { int l = S.top().getFirstGreater(h) ; ret += S.top().cut(h, l) ; S.top().y=l-1 ; } cout << ret << "\n" ; //endl ; S.push(segment(-segment::addA,h, (S.empty()? 1 : S.top().y+1),MAXX)) ; } } }
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 110 111 112 113 114 115 116 117 | #include <iostream> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <stack> #include <cmath> #include <cassert> #include <cstring> #include <ext/numeric> using namespace std ; using namespace __gnu_cxx ; typedef long long LL ; typedef pair<int,int> PII ; typedef vector<int> VI ; const int INF = 1e9+100 ; const LL INFLL = (LL)INF * (LL)INF ; #define REP(i,n) for(i=0;i<(n);++i) #define ALL(c) c.begin(),c.end() #define VAR(v,i) __typeof(i) v=(i) #define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i) #define CLEAR(t) memset(t,0,sizeof(t)) #define PB push_back #define MP make_pair #define FI first #define SE second template<class T1,class T2> ostream& operator<<(ostream &s, const pair<T1,T2> &x) { s<< "(" << x.FI << "," << x.SE << ")"; return s;} template<class T> ostream& operator<<(ostream &s, const vector<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T> ostream& operator<<(ostream &s, const set<T> &t) { FOREACH(it, t) s << *it << " " ; return s ; } template<class T1,class T2> ostream& operator<<(ostream &s, const map<T1, T2> &t) { FOREACH(it, t) s << *it << " " ; return s ; } /////////////////////////////////////////// const int MAXX = 1000100 ; int counter[MAXX+1] ; LL sum[MAXX+1] ; struct segment { static LL addA ; LL a_, b ; int x, y ; segment(LL aa, LL bb, int xx, int yy) : a_(aa), b(bb), x(xx), y(yy) {} LL getVal(int p) const { //assert(x<=p && p<=y) ; return (a_+addA)*p + b ; } LL getLastVal() const { return getVal(y) ; } LL getFirstVal() const { return getVal(x) ; } int getFirstGreater(LL h) const { //assert(h<=getLastVal()) ; LL a = a_+addA ; //assert(a>0) ; //assert(h-b>=0) ; int ret = ((h-b)+(a-1))/a ; //assert(x<ret && ret<=y) ; return ret ; } LL cut(LL h, int p=-INF) const { //assert(p<=y) ; p = max(p, x) ; return (a_+addA)*(sum[y]-sum[p-1]) + (b-h)*(counter[y]-counter[p-1]) ; } } ; LL segment::addA=0 ; int main() { ios_base::sync_with_stdio(0) ; int n, m, i, x, MAXX=0 ; // przyslania cin >> n >> m ; REP(i,n) { cin >> x ; counter[x]++ ; MAXX = max(MAXX, x) ; } for(i=1 ; i<=MAXX ; i++) { sum[i] = sum[i-1] + (LL)i*counter[i] ; counter[i] += counter[i-1] ; } stack<segment> S ; S.push(segment(0,0, 1,MAXX)) ; LL d, h, prev_d=0 ; while(m--) { LL d, h ; cin >> d >> h ; segment::addA += d-prev_d ; prev_d = d ; if(S.top().getLastVal()<h) cout << 0 << endl ; else { LL ret = 0 ; while(!S.empty() && h<=S.top().getFirstVal()) { ret += S.top().cut(h) ; S.pop() ; } if(!S.empty() && h<=S.top().getLastVal()) { int l = S.top().getFirstGreater(h) ; ret += S.top().cut(h, l) ; S.top().y=l-1 ; } cout << ret << "\n" ; //endl ; S.push(segment(-segment::addA,h, (S.empty()? 1 : S.top().y+1),MAXX)) ; } } } |