#include <iostream> #include <vector> #include <cstdio> #include <algorithm> #define ll long long #define int long long using namespace std; int n, m; struct ciecie { ll siano; ll p, k; ll wys, cz; ciecie() { siano = 0; p = 0; k = 0; wys = 0; cz = 0; } ciecie(ll a, ll e, ll b, ll c, ll d) { siano = d; p = b; k = c; wys = a; cz = e; } }; vector < ciecie > V; ll v[500005], vs[500005]; ll znajdz_wysokosc(ll miejsce, ll czas) { if (V.size() == 0 || V[0].p > miejsce) return czas*v[miejsce]; int p = 0, k = V.size()-1; while(p < k-1) { int s = (p + k)/2; if (V[s].p <= miejsce) p = s; else k = s; } if (V[V.size()-1].p <= miejsce) p = V.size()-1; return V[p].wys + v[miejsce] * (czas - V[p].cz); } ll znajdz_miejsce_ciecia(ll cz, ll wys) { if (znajdz_wysokosc(1, cz) > wys) return 1; if (znajdz_wysokosc(n, cz) <= wys) { //cout<<"B"<<znajdz_wysokosc(n, cz)<<" "<<wys<<endl; return -1; } int p = 1, k = n; while(p < k - 1) { int s = (p+k)/2; if (znajdz_wysokosc(s, cz) <= wys) p = s; else k = s; } return k; } ll dodaj_ciecie(ll miejsce, ll cz, ll wys) { ll wynik = 0; while(V.size()>0 && V[V.size()-1].k >= miejsce) { ciecie c = V[V.size()-1]; V.pop_back(); ll dl = c.k - max(c.p, miejsce) + 1; wynik += c.wys*dl + (vs[c.k] - vs[max(c.p, miejsce)-1]) * (cz - c.cz) - dl * wys; if (c.p < miejsce) { c.k = miejsce - 1; V.push_back(c); } } V.push_back( ciecie(wys, cz, miejsce, n, wynik)); return wynik; } void wypisz_vector() { for(int i=0; i<V.size(); i++) { cout << V[i].cz<<" "<<V[i].wys<<" "<<V[i].p<<" "<<V[i].k<<endl; } } main() { scanf("%lld%lld", &n, &m); V.push_back(ciecie(0, 0, 1, n, 0)); for(int i=1; i<=n; i++) scanf("%lld", &v[i]); sort(v+1, v+n+1); for(int i=1; i<=n; i++) vs[i] = vs[i-1] + v[i]; ll cz, wys; while(m--) { scanf("%lld%lld", &cz, &wys); ll miejsce = znajdz_miejsce_ciecia(cz, wys); //cout<<"A"<<miejsce<<"A"; if (miejsce != -1) printf("%lld\n", dodaj_ciecie(miejsce, cz, wys)); else printf("0\n"); //wypisz_vector(); } 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 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 118 119 120 121 122 123 124 | #include <iostream> #include <vector> #include <cstdio> #include <algorithm> #define ll long long #define int long long using namespace std; int n, m; struct ciecie { ll siano; ll p, k; ll wys, cz; ciecie() { siano = 0; p = 0; k = 0; wys = 0; cz = 0; } ciecie(ll a, ll e, ll b, ll c, ll d) { siano = d; p = b; k = c; wys = a; cz = e; } }; vector < ciecie > V; ll v[500005], vs[500005]; ll znajdz_wysokosc(ll miejsce, ll czas) { if (V.size() == 0 || V[0].p > miejsce) return czas*v[miejsce]; int p = 0, k = V.size()-1; while(p < k-1) { int s = (p + k)/2; if (V[s].p <= miejsce) p = s; else k = s; } if (V[V.size()-1].p <= miejsce) p = V.size()-1; return V[p].wys + v[miejsce] * (czas - V[p].cz); } ll znajdz_miejsce_ciecia(ll cz, ll wys) { if (znajdz_wysokosc(1, cz) > wys) return 1; if (znajdz_wysokosc(n, cz) <= wys) { //cout<<"B"<<znajdz_wysokosc(n, cz)<<" "<<wys<<endl; return -1; } int p = 1, k = n; while(p < k - 1) { int s = (p+k)/2; if (znajdz_wysokosc(s, cz) <= wys) p = s; else k = s; } return k; } ll dodaj_ciecie(ll miejsce, ll cz, ll wys) { ll wynik = 0; while(V.size()>0 && V[V.size()-1].k >= miejsce) { ciecie c = V[V.size()-1]; V.pop_back(); ll dl = c.k - max(c.p, miejsce) + 1; wynik += c.wys*dl + (vs[c.k] - vs[max(c.p, miejsce)-1]) * (cz - c.cz) - dl * wys; if (c.p < miejsce) { c.k = miejsce - 1; V.push_back(c); } } V.push_back( ciecie(wys, cz, miejsce, n, wynik)); return wynik; } void wypisz_vector() { for(int i=0; i<V.size(); i++) { cout << V[i].cz<<" "<<V[i].wys<<" "<<V[i].p<<" "<<V[i].k<<endl; } } main() { scanf("%lld%lld", &n, &m); V.push_back(ciecie(0, 0, 1, n, 0)); for(int i=1; i<=n; i++) scanf("%lld", &v[i]); sort(v+1, v+n+1); for(int i=1; i<=n; i++) vs[i] = vs[i-1] + v[i]; ll cz, wys; while(m--) { scanf("%lld%lld", &cz, &wys); ll miejsce = znajdz_miejsce_ciecia(cz, wys); //cout<<"A"<<miejsce<<"A"; if (miejsce != -1) printf("%lld\n", dodaj_ciecie(miejsce, cz, wys)); else printf("0\n"); //wypisz_vector(); } return 0; } |