#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<long long>::iterator up(vector<long long>::iterator beg, vector<long long>::iterator end, long long b, long long d){ vector<long long>::iterator it; int count = std::distance(beg,end),step; while (count>0) { it = beg; step=count/2; std::advance (it,step); if (!(b<*it*d)) { beg=++it; count-=step+1; } else count=step; } return beg; } int main(){ ios_base::sync_with_stdio(0); long long n,m; cin>>n>>m; vector<long long> wzr; for(int i=0;i<n;++i){long long a; cin>>a; wzr.push_back(a);} sort(wzr.begin(),wzr.end()); vector<long long> acc(n,0); acc[n-1]=wzr[n-1]; for(int i=n-2;i>=0;--i){acc[i]=acc[i+1]+wzr[i];} long long tot_kg=0; for(int j=0;j<m;++j){ long long b=0,d=0; cin>>d>>b; long long it=distance(wzr.begin(),up(wzr.begin(),wzr.end(),b,d)); long long x; x=d*acc[it]-b*(n-it); if(x-tot_kg>0)x-=tot_kg; else x=0; cout<<(long long)x<<endl; tot_kg+=x; //cout<<tot_kg<<endl; } }
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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<long long>::iterator up(vector<long long>::iterator beg, vector<long long>::iterator end, long long b, long long d){ vector<long long>::iterator it; int count = std::distance(beg,end),step; while (count>0) { it = beg; step=count/2; std::advance (it,step); if (!(b<*it*d)) { beg=++it; count-=step+1; } else count=step; } return beg; } int main(){ ios_base::sync_with_stdio(0); long long n,m; cin>>n>>m; vector<long long> wzr; for(int i=0;i<n;++i){long long a; cin>>a; wzr.push_back(a);} sort(wzr.begin(),wzr.end()); vector<long long> acc(n,0); acc[n-1]=wzr[n-1]; for(int i=n-2;i>=0;--i){acc[i]=acc[i+1]+wzr[i];} long long tot_kg=0; for(int j=0;j<m;++j){ long long b=0,d=0; cin>>d>>b; long long it=distance(wzr.begin(),up(wzr.begin(),wzr.end(),b,d)); long long x; x=d*acc[it]-b*(n-it); if(x-tot_kg>0)x-=tot_kg; else x=0; cout<<(long long)x<<endl; tot_kg+=x; //cout<<tot_kg<<endl; } } |