#include <iostream> #include <algorithm> #include <set> using namespace std; const int N=500005; long long d, b; long long sumyA[N+1];//[n] - do n-1 wlacznie int a[N]; struct Ciach { long long cb, cd; int indA; bool szukanie; Ciach(long long b, long long d, int ind) : cb(b), cd(d), indA(ind), szukanie(false) {} Ciach(bool szuk) : cb(0), cd(0), indA(0), szukanie(szuk) {} bool operator<(const Ciach &c) const { if (szukanie) return b<c.wys(); if (c.szukanie) return wys()<b; return indA<c.indA; } long long wys() const { return (d-cd)*a[indA]+cb; } }; int main() { ios_base::sync_with_stdio(false); int n, m; cin>>n>>m; for (int i=0; i<n; ++i) cin>>a[i]; sort(a, a+n); for (int i=0; i<n; ++i) sumyA[i+1]=sumyA[i]+a[i]; set<Ciach> ciachy; ciachy.insert(Ciach(0, 0, 0)); Ciach szuk(true); for (int i=0; i<m; ++i) { cin>>d>>b; long long wyn=0; set<Ciach>::iterator it=ciachy.upper_bound(szuk), it1=it, it2=it; while (it1!=ciachy.end()) { const Ciach &c=*it1; ++it1; int kon= it1==ciachy.end() ? n : it1->indA; wyn+=(d-c.cd)*(sumyA[kon]-sumyA[c.indA])+(kon-c.indA)*(c.cb-b); } int nowyPocz; if (it==ciachy.begin()) nowyPocz=0; else { int kon= it==ciachy.end() ? n : it->indA; const Ciach &poprz=*--it2; nowyPocz=kon; long long lDni=d-poprz.cd; int l=poprz.indA, p=kon; while (l<p) { int sr=(l+p)/2; if (poprz.cb+lDni*a[sr]<=b) l=sr+1; else p=sr; } if (l<kon && b<poprz.cb+lDni*a[l]) { wyn+=lDni*(sumyA[kon]-sumyA[l])+(kon-l)*(poprz.cb-b); nowyPocz=l; } } ciachy.erase(it, ciachy.end()); if (nowyPocz<n) ciachy.insert(Ciach(b, d, nowyPocz)); cout<<wyn<<'\n'; } 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 | #include <iostream> #include <algorithm> #include <set> using namespace std; const int N=500005; long long d, b; long long sumyA[N+1];//[n] - do n-1 wlacznie int a[N]; struct Ciach { long long cb, cd; int indA; bool szukanie; Ciach(long long b, long long d, int ind) : cb(b), cd(d), indA(ind), szukanie(false) {} Ciach(bool szuk) : cb(0), cd(0), indA(0), szukanie(szuk) {} bool operator<(const Ciach &c) const { if (szukanie) return b<c.wys(); if (c.szukanie) return wys()<b; return indA<c.indA; } long long wys() const { return (d-cd)*a[indA]+cb; } }; int main() { ios_base::sync_with_stdio(false); int n, m; cin>>n>>m; for (int i=0; i<n; ++i) cin>>a[i]; sort(a, a+n); for (int i=0; i<n; ++i) sumyA[i+1]=sumyA[i]+a[i]; set<Ciach> ciachy; ciachy.insert(Ciach(0, 0, 0)); Ciach szuk(true); for (int i=0; i<m; ++i) { cin>>d>>b; long long wyn=0; set<Ciach>::iterator it=ciachy.upper_bound(szuk), it1=it, it2=it; while (it1!=ciachy.end()) { const Ciach &c=*it1; ++it1; int kon= it1==ciachy.end() ? n : it1->indA; wyn+=(d-c.cd)*(sumyA[kon]-sumyA[c.indA])+(kon-c.indA)*(c.cb-b); } int nowyPocz; if (it==ciachy.begin()) nowyPocz=0; else { int kon= it==ciachy.end() ? n : it->indA; const Ciach &poprz=*--it2; nowyPocz=kon; long long lDni=d-poprz.cd; int l=poprz.indA, p=kon; while (l<p) { int sr=(l+p)/2; if (poprz.cb+lDni*a[sr]<=b) l=sr+1; else p=sr; } if (l<kon && b<poprz.cb+lDni*a[l]) { wyn+=lDni*(sumyA[kon]-sumyA[l])+(kon-l)*(poprz.cb-b); nowyPocz=l; } } ciachy.erase(it, ciachy.end()); if (nowyPocz<n) ciachy.insert(Ciach(b, d, nowyPocz)); cout<<wyn<<'\n'; } return 0; } |