// tested by Hightail: https://github.com/dj3500/hightail #include <iostream> #include <cstdio> #include <string> #include <vector> #include <set> #include <map> #include <queue> #include <cmath> #include <algorithm> #include <sstream> #include <stack> #include <cstring> #include <iomanip> #include <ctime> #include <cassert> using namespace std; #define pb push_back #define INF 1001001001 #define FOR(i,n) for(int (i)=0;(i)<(n);++(i)) #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i)) #define mp make_pair #define pii pair<int,int> #define ll long long #define vi vector<int> #define SZ(x) ((int)((x).size())) #define fi first #define se second #define wez(n) int (n); scanf("%d",&(n)); #define wez2(n,m) int (n),(m); scanf("%d %d",&(n),&(m)); #define wez3(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k)); inline void pisz(int n) { printf("%d\n",n); } template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";} template<typename T> ostream& operator<<(ostream &s,vector<T> t){FOR(i,SZ(t))s<<t[i]<<" ";return s; } #define DBG(vari) cout<<"["<<__LINE__<<"] "<<#vari<<" = "<<(vari)<<endl; #define ALL(t) t.begin(),t.end() #define FOREACH(i,t) for (__typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define TESTS wez(testow)while(testow--) #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i) #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i) #define REMAX(a,b) (a)=max((a),(b)); #define REMIN(a,b) (a)=min((a),(b)); #define IOS ios_base::sync_with_stdio(0); const int N = 500007; ll a[N], prefsum[N]; struct S { int l, r; ll d, b; }; int main () { wez2(n,m); FORI(i,n) scanf("%lld", a+i); sort(a+1, a+n+1); FORI(i,n) prefsum[i] = prefsum[i-1] + a[i]; vector<S> q = {{1,n,0,0}}; while (m--) { ll dnow, bnow; scanf("%lld %lld", &dnow, &bnow); ll res = 0; while (!q.empty()) { S s = q.back(); if (bnow <= s.b + a[s.l] * (dnow - s.d)) { // cale do sciecia res += (s.b - bnow) * (s.r - s.l + 1) + (prefsum[s.r] - prefsum[s.l-1]) * (dnow - s.d); q.pop_back(); } else if (bnow <= s.b + a[s.r] * (dnow - s.d)) { // czesc do sciecia int mini = s.r, from = s.l + 1, to = s.r - 1; while (from <= to) { int mid = (from + to) / 2; if (bnow <= s.b + a[mid] * (dnow - s.d)) { mini = mid; to = mid - 1; } else { from = mid + 1; } } // s.l ... mini-1 nie do sciecia, mini ... s.r do sciecia q.pop_back(); q.pb({s.l, mini-1, s.d, s.b}); q.pb({mini, s.r, s.d, s.b}); } else { // nic do sciecia break; } } int l = q.empty() ? 1 : q.back().r + 1; if (l <= n) q.pb({l, n, dnow, bnow}); printf("%lld\n", res); } }
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 | // tested by Hightail: https://github.com/dj3500/hightail #include <iostream> #include <cstdio> #include <string> #include <vector> #include <set> #include <map> #include <queue> #include <cmath> #include <algorithm> #include <sstream> #include <stack> #include <cstring> #include <iomanip> #include <ctime> #include <cassert> using namespace std; #define pb push_back #define INF 1001001001 #define FOR(i,n) for(int (i)=0;(i)<(n);++(i)) #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i)) #define mp make_pair #define pii pair<int,int> #define ll long long #define vi vector<int> #define SZ(x) ((int)((x).size())) #define fi first #define se second #define wez(n) int (n); scanf("%d",&(n)); #define wez2(n,m) int (n),(m); scanf("%d %d",&(n),&(m)); #define wez3(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k)); inline void pisz(int n) { printf("%d\n",n); } template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";} template<typename T> ostream& operator<<(ostream &s,vector<T> t){FOR(i,SZ(t))s<<t[i]<<" ";return s; } #define DBG(vari) cout<<"["<<__LINE__<<"] "<<#vari<<" = "<<(vari)<<endl; #define ALL(t) t.begin(),t.end() #define FOREACH(i,t) for (__typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define TESTS wez(testow)while(testow--) #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i) #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i) #define REMAX(a,b) (a)=max((a),(b)); #define REMIN(a,b) (a)=min((a),(b)); #define IOS ios_base::sync_with_stdio(0); const int N = 500007; ll a[N], prefsum[N]; struct S { int l, r; ll d, b; }; int main () { wez2(n,m); FORI(i,n) scanf("%lld", a+i); sort(a+1, a+n+1); FORI(i,n) prefsum[i] = prefsum[i-1] + a[i]; vector<S> q = {{1,n,0,0}}; while (m--) { ll dnow, bnow; scanf("%lld %lld", &dnow, &bnow); ll res = 0; while (!q.empty()) { S s = q.back(); if (bnow <= s.b + a[s.l] * (dnow - s.d)) { // cale do sciecia res += (s.b - bnow) * (s.r - s.l + 1) + (prefsum[s.r] - prefsum[s.l-1]) * (dnow - s.d); q.pop_back(); } else if (bnow <= s.b + a[s.r] * (dnow - s.d)) { // czesc do sciecia int mini = s.r, from = s.l + 1, to = s.r - 1; while (from <= to) { int mid = (from + to) / 2; if (bnow <= s.b + a[mid] * (dnow - s.d)) { mini = mid; to = mid - 1; } else { from = mid + 1; } } // s.l ... mini-1 nie do sciecia, mini ... s.r do sciecia q.pop_back(); q.pb({s.l, mini-1, s.d, s.b}); q.pb({mini, s.r, s.d, s.b}); } else { // nic do sciecia break; } } int l = q.empty() ? 1 : q.back().r + 1; if (l <= n) q.pb({l, n, dnow, bnow}); printf("%lld\n", res); } } |