//Przemysław Jakub Kozłowski #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #define FI first #define SE second #define MP make_pair using namespace std; typedef long long LL; const int W = 1000006; inline LL dzsuf(LL a, LL b) {return (a+b-1)/b;} int n,m; int w; int ilepref[W]; LL sumpref[W]; vector<pair<int, pair<LL, LL> > > stos; int main() { scanf("%d%d", &n, &m); for(int i = 1;i <= n;i++) { int a; scanf("%d", &a); w = max(w, a); ilepref[a]++; } for(int i = 1;i <= w;i++) { sumpref[i] = sumpref[i-1]+(LL)ilepref[i]*i; ilepref[i] += ilepref[i-1]; } stos.push_back(MP(1, MP(0, 0))); for(int i = 1;i <= m;i++) { LL d, b; scanf("%lld%lld", &d, &b); int psko = w+1; // Pierwsza skoszona pozycja int psto = stos.size()-1; // Przedzial stosu, w którym jest pierwsza skoszona pozycja while(psto > 0 && stos[psto-1].SE.SE+(d-stos[psto-1].SE.FI)*(stos[psto].FI-1) >= b) psto--; LL skos = dzsuf(b-stos[psto].SE.SE, d-stos[psto].SE.FI); // Pierwsza skoszona pozycja if(skos < stos[psto].FI) psko = stos[psto].FI; else if(skos > w || (psto <= (int)stos.size()-2 && stos[psto+1].FI <= skos)) psko = w+1; else psko = skos; LL wyn = 0; if(psko != w+1) { int last = w+1; while(stos.size() > 0 && ((int)stos.size()-1 > psto || stos.back().FI == psko)) { int curr = stos.back().FI; LL pwys = stos.back().SE.SE; LL pdzi = stos.back().SE.FI; LL suma = pwys*(ilepref[last-1]-ilepref[curr-1])+(d-pdzi)*(sumpref[last-1]-sumpref[curr-1]); wyn += suma-b*(ilepref[last-1]-ilepref[curr-1]); last = curr; stos.pop_back(); } if(psto == (int)stos.size()-1) { int curr = psko; LL pwys = stos.back().SE.SE; LL pdzi = stos.back().SE.FI; LL suma = pwys*(ilepref[last-1]-ilepref[curr-1])+(d-pdzi)*(sumpref[last-1]-sumpref[curr-1]); wyn += suma-b*(ilepref[last-1]-ilepref[curr-1]); } stos.push_back(MP(psko, MP(d, b))); } /*cerr << "Stos.size(): " << stos.size() << endl; for(int i = 0;i < stos.size();i++) cerr << "I: " << i << " stos[i]: " << stos[i].FI << " " << stos[i].SE.FI << " " << stos[i].SE.SE << endl;*/ printf("%lld\n", wyn); } 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 | //Przemysław Jakub Kozłowski #include <iostream> #include <cstdio> #include <algorithm> #include <vector> #define FI first #define SE second #define MP make_pair using namespace std; typedef long long LL; const int W = 1000006; inline LL dzsuf(LL a, LL b) {return (a+b-1)/b;} int n,m; int w; int ilepref[W]; LL sumpref[W]; vector<pair<int, pair<LL, LL> > > stos; int main() { scanf("%d%d", &n, &m); for(int i = 1;i <= n;i++) { int a; scanf("%d", &a); w = max(w, a); ilepref[a]++; } for(int i = 1;i <= w;i++) { sumpref[i] = sumpref[i-1]+(LL)ilepref[i]*i; ilepref[i] += ilepref[i-1]; } stos.push_back(MP(1, MP(0, 0))); for(int i = 1;i <= m;i++) { LL d, b; scanf("%lld%lld", &d, &b); int psko = w+1; // Pierwsza skoszona pozycja int psto = stos.size()-1; // Przedzial stosu, w którym jest pierwsza skoszona pozycja while(psto > 0 && stos[psto-1].SE.SE+(d-stos[psto-1].SE.FI)*(stos[psto].FI-1) >= b) psto--; LL skos = dzsuf(b-stos[psto].SE.SE, d-stos[psto].SE.FI); // Pierwsza skoszona pozycja if(skos < stos[psto].FI) psko = stos[psto].FI; else if(skos > w || (psto <= (int)stos.size()-2 && stos[psto+1].FI <= skos)) psko = w+1; else psko = skos; LL wyn = 0; if(psko != w+1) { int last = w+1; while(stos.size() > 0 && ((int)stos.size()-1 > psto || stos.back().FI == psko)) { int curr = stos.back().FI; LL pwys = stos.back().SE.SE; LL pdzi = stos.back().SE.FI; LL suma = pwys*(ilepref[last-1]-ilepref[curr-1])+(d-pdzi)*(sumpref[last-1]-sumpref[curr-1]); wyn += suma-b*(ilepref[last-1]-ilepref[curr-1]); last = curr; stos.pop_back(); } if(psto == (int)stos.size()-1) { int curr = psko; LL pwys = stos.back().SE.SE; LL pdzi = stos.back().SE.FI; LL suma = pwys*(ilepref[last-1]-ilepref[curr-1])+(d-pdzi)*(sumpref[last-1]-sumpref[curr-1]); wyn += suma-b*(ilepref[last-1]-ilepref[curr-1]); } stos.push_back(MP(psko, MP(d, b))); } /*cerr << "Stos.size(): " << stos.size() << endl; for(int i = 0;i < stos.size();i++) cerr << "I: " << i << " stos[i]: " << stos[i].FI << " " << stos[i].SE.FI << " " << stos[i].SE.SE << endl;*/ printf("%lld\n", wyn); } return 0; } |