#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int N = 1e6; vector <int> Wzrost; long long T_Pref[N]; vector < pair < pair <int,int>, pair<long long,long long> > > K; inline int Wyszukaj(int p,int k,long long t,long long b,pair <long long,long long> war){ int s; long long a_wys; pair <long long,long long> zmiana; while(p<k){ s = (p+k+1)/2; a_wys = war.second+(t-war.first)*(long long)Wzrost[s]; if(a_wys >= b) k = s-1; else p = s; } return p; } inline long long S_Pref(int p,int k){ if(p>k) return 0; return T_Pref[k+1]-T_Pref[p]; } inline void Wczytaj(int n){ int i,a; for(i=0; i<n; i++){ scanf("%d", &a); Wzrost.push_back(a); } } inline bool Sprawdz(int p,long long t,long long b,pair <long long,long long> war){ long long a_wys; a_wys = war.second+(t-war.first)*(long long)Wzrost[p]; if(a_wys>= b) return true; return false; } int main(){ pair <long long,long long> a_para; long long t,b,a_wynik,d; int n,m; int j,i,x,p,k; scanf("%d%d", &n,&m); Wczytaj(n); sort(Wzrost.begin(),Wzrost.end()); for(i=0; i<n; i++){ T_Pref[i+1] = T_Pref[i]+(long long)Wzrost[i]; K.push_back(make_pair( make_pair(i,i),make_pair(0,0) )); } for(i=0; i<m; i++){ scanf("%lld%lld", &t,&b); a_wynik = 0; while(!K.empty() && Sprawdz( K.back().first.first,t,b,K.back().second ) ) { d = (long long)(K.back().first.second)-(long long)(K.back().first.first)+1; a_wynik += d*(K.back().second.second-b)+S_Pref(K.back().first.first,K.back().first.second)*(t-K.back().second.first); K.pop_back(); } if(K.size()==0) K.push_back(make_pair(make_pair(0,n-1),make_pair(t,b))); else{ p = K.back().first.first; k = K.back().first.second; x = Wyszukaj(p,k,t,b,K.back().second); x++; a_para = K.back().second; a_wynik += S_Pref(x,k)*(t-K.back().second.first)-(long long)(k-x+1)*(b-K.back().second.second); K.pop_back(); K.push_back( make_pair( make_pair(p,x-1),a_para ) ); if(x!=n) K.push_back( make_pair( make_pair(x,n-1), make_pair(t,b) ) ); } printf("%lld\n", a_wynik); } 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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int N = 1e6; vector <int> Wzrost; long long T_Pref[N]; vector < pair < pair <int,int>, pair<long long,long long> > > K; inline int Wyszukaj(int p,int k,long long t,long long b,pair <long long,long long> war){ int s; long long a_wys; pair <long long,long long> zmiana; while(p<k){ s = (p+k+1)/2; a_wys = war.second+(t-war.first)*(long long)Wzrost[s]; if(a_wys >= b) k = s-1; else p = s; } return p; } inline long long S_Pref(int p,int k){ if(p>k) return 0; return T_Pref[k+1]-T_Pref[p]; } inline void Wczytaj(int n){ int i,a; for(i=0; i<n; i++){ scanf("%d", &a); Wzrost.push_back(a); } } inline bool Sprawdz(int p,long long t,long long b,pair <long long,long long> war){ long long a_wys; a_wys = war.second+(t-war.first)*(long long)Wzrost[p]; if(a_wys>= b) return true; return false; } int main(){ pair <long long,long long> a_para; long long t,b,a_wynik,d; int n,m; int j,i,x,p,k; scanf("%d%d", &n,&m); Wczytaj(n); sort(Wzrost.begin(),Wzrost.end()); for(i=0; i<n; i++){ T_Pref[i+1] = T_Pref[i]+(long long)Wzrost[i]; K.push_back(make_pair( make_pair(i,i),make_pair(0,0) )); } for(i=0; i<m; i++){ scanf("%lld%lld", &t,&b); a_wynik = 0; while(!K.empty() && Sprawdz( K.back().first.first,t,b,K.back().second ) ) { d = (long long)(K.back().first.second)-(long long)(K.back().first.first)+1; a_wynik += d*(K.back().second.second-b)+S_Pref(K.back().first.first,K.back().first.second)*(t-K.back().second.first); K.pop_back(); } if(K.size()==0) K.push_back(make_pair(make_pair(0,n-1),make_pair(t,b))); else{ p = K.back().first.first; k = K.back().first.second; x = Wyszukaj(p,k,t,b,K.back().second); x++; a_para = K.back().second; a_wynik += S_Pref(x,k)*(t-K.back().second.first)-(long long)(k-x+1)*(b-K.back().second.second); K.pop_back(); K.push_back( make_pair( make_pair(p,x-1),a_para ) ); if(x!=n) K.push_back( make_pair( make_pair(x,n-1), make_pair(t,b) ) ); } printf("%lld\n", a_wynik); } return 0; } |