#include <algorithm> #include <cstdio> #include <functional> #include <vector> using namespace std; typedef long long i64; struct Trim { i64 t_,h_; int k_; Trim(i64 t, i64 h, int k) : t_(t), h_(h), k_(k) {} }; struct Problem { Problem(int n) : n_(n), a_(n), as_(n+1) {} void prepare(); inline i64 as(int i, int j) { return as_[j+1] - as_[i]; } inline i64 getH(int i, i64 t, const Trim& trim) { return trim.h_ + (t-trim.t_)*a_[i]; } inline i64 getSum(int i, int j, i64 t, i64 h, const Trim& trim) { return as(i,j)*(t-trim.t_) + (trim.h_-h)*(j-i+1); } int binSearch(int i, int j, i64 t, i64 h, const Trim& trim); i64 next(i64 t, i64 h); int n_; vector<int> a_; vector<i64> as_; vector<Trim> trims_; }; void Problem::prepare() { sort(a_.begin(), a_.end(), greater<int>()); for (int i=1; i<=n_; ++i) as_[i] = as_[i-1] + a_[i-1]; trims_.emplace_back(0,0,n_-1); } int Problem::binSearch(int i, int j, i64 t, i64 h, const Trim& trim) { while (i < j) { int k = (i+j+1)/2; if (getH(k,t,trim) > h) i = k; else j = k-1; } return i; } i64 Problem::next(i64 t, i64 h) { i64 result = 0; int k = -1; for (int i=0; i<n_; ++i) { Trim trim = trims_.back(); if (getH(i,t,trim) <= h) break; int j = trim.k_; if (getH(j,t,trim) <= h) { k = binSearch(i,j,t,h,trim); result += getSum(i,k,t,h,trim); break; } trims_.pop_back(); result += getSum(i,j,t,h,trim); i = j; k = j; } if (k != -1) trims_.emplace_back(t,h,k); return result; } int main() { int n,m; scanf("%d%d", &n, &m); Problem p(n); for (int& x : p.a_) scanf("%d", &x); p.prepare(); for (int i=0; i<m; ++i) { i64 t,h; scanf("%lld%lld", &t, &h); printf("%lld\n", p.next(t,h)); } }
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 | #include <algorithm> #include <cstdio> #include <functional> #include <vector> using namespace std; typedef long long i64; struct Trim { i64 t_,h_; int k_; Trim(i64 t, i64 h, int k) : t_(t), h_(h), k_(k) {} }; struct Problem { Problem(int n) : n_(n), a_(n), as_(n+1) {} void prepare(); inline i64 as(int i, int j) { return as_[j+1] - as_[i]; } inline i64 getH(int i, i64 t, const Trim& trim) { return trim.h_ + (t-trim.t_)*a_[i]; } inline i64 getSum(int i, int j, i64 t, i64 h, const Trim& trim) { return as(i,j)*(t-trim.t_) + (trim.h_-h)*(j-i+1); } int binSearch(int i, int j, i64 t, i64 h, const Trim& trim); i64 next(i64 t, i64 h); int n_; vector<int> a_; vector<i64> as_; vector<Trim> trims_; }; void Problem::prepare() { sort(a_.begin(), a_.end(), greater<int>()); for (int i=1; i<=n_; ++i) as_[i] = as_[i-1] + a_[i-1]; trims_.emplace_back(0,0,n_-1); } int Problem::binSearch(int i, int j, i64 t, i64 h, const Trim& trim) { while (i < j) { int k = (i+j+1)/2; if (getH(k,t,trim) > h) i = k; else j = k-1; } return i; } i64 Problem::next(i64 t, i64 h) { i64 result = 0; int k = -1; for (int i=0; i<n_; ++i) { Trim trim = trims_.back(); if (getH(i,t,trim) <= h) break; int j = trim.k_; if (getH(j,t,trim) <= h) { k = binSearch(i,j,t,h,trim); result += getSum(i,k,t,h,trim); break; } trims_.pop_back(); result += getSum(i,j,t,h,trim); i = j; k = j; } if (k != -1) trims_.emplace_back(t,h,k); return result; } int main() { int n,m; scanf("%d%d", &n, &m); Problem p(n); for (int& x : p.a_) scanf("%d", &x); p.prepare(); for (int i=0; i<m; ++i) { i64 t,h; scanf("%lld%lld", &t, &h); printf("%lld\n", p.next(t,h)); } } |