#include <algorithm> #include <cstdio> #include <iostream> #include <stack> #include <vector> using namespace std; class Cut { public: Cut() : left_(0), base_(0), day_(0) {} Cut(const int left, const long long base, const long long day) : left_(left), base_(base), day_(day) {} int left() const { return left_; } long long GetWeight(const Cut& cut, const vector<long long>& sums) const { if (left_ >= sums.size()) return 0; return sums[left_] * (day_ - cut.day_) - (base_ - cut.base_) * (sums.size() - left_); } bool IsAbove( const vector<int>& a, const long long d, const long long b) const { if (left_ >= a.size()) return true; return GetHeight(a, d, left_) >= b; } Cut SubCut(const vector<int>& a, const long long d, const long long b) const { // TODO: This is a linear function, can be done in O(1). int left = left_; int right = a.size(); while (left + 1 < right) { const int m = (left + right) / 2; if (GetHeight(a, d, m) <= b) left = m + 1; else right = m; } if (GetHeight(a, d, left) <= b) ++left; // cerr << "New cut " << left << ' ' << b << ' ' << d << endl; return Cut(left, b, d); } private: long long GetHeight( const vector<int>&a, const long long d, const int i) const { return base_ + a[i] * (d - day_); } int left_; long long base_; long long day_; }; int main() { int n; int m; scanf("%d%d", &n, &m); vector<int> a(n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); sort(a.begin(), a.end()); // Init structures. stack<Cut> s; s.push(Cut()); vector<long long> sums(n); sums[n - 1] = a[n - 1]; for (int i = n - 1; i > 0; --i) sums[i - 1] = sums[i] + a[i - 1]; while (m--) { long long d; long long b; scanf("%lld%lld", &d, &b); long long w = 0; // Undo cuts covered by the current one. while (s.size() > 1 && s.top().IsAbove(a, d, b)) { const Cut cut = s.top(); s.pop(); w -= cut.GetWeight(s.top(), sums); } // Add current cut. const Cut cut = s.top().SubCut(a, d, b); w += cut.GetWeight(s.top(), sums); s.push(cut); printf("%lld\n", w); } 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 <algorithm> #include <cstdio> #include <iostream> #include <stack> #include <vector> using namespace std; class Cut { public: Cut() : left_(0), base_(0), day_(0) {} Cut(const int left, const long long base, const long long day) : left_(left), base_(base), day_(day) {} int left() const { return left_; } long long GetWeight(const Cut& cut, const vector<long long>& sums) const { if (left_ >= sums.size()) return 0; return sums[left_] * (day_ - cut.day_) - (base_ - cut.base_) * (sums.size() - left_); } bool IsAbove( const vector<int>& a, const long long d, const long long b) const { if (left_ >= a.size()) return true; return GetHeight(a, d, left_) >= b; } Cut SubCut(const vector<int>& a, const long long d, const long long b) const { // TODO: This is a linear function, can be done in O(1). int left = left_; int right = a.size(); while (left + 1 < right) { const int m = (left + right) / 2; if (GetHeight(a, d, m) <= b) left = m + 1; else right = m; } if (GetHeight(a, d, left) <= b) ++left; // cerr << "New cut " << left << ' ' << b << ' ' << d << endl; return Cut(left, b, d); } private: long long GetHeight( const vector<int>&a, const long long d, const int i) const { return base_ + a[i] * (d - day_); } int left_; long long base_; long long day_; }; int main() { int n; int m; scanf("%d%d", &n, &m); vector<int> a(n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); sort(a.begin(), a.end()); // Init structures. stack<Cut> s; s.push(Cut()); vector<long long> sums(n); sums[n - 1] = a[n - 1]; for (int i = n - 1; i > 0; --i) sums[i - 1] = sums[i] + a[i - 1]; while (m--) { long long d; long long b; scanf("%lld%lld", &d, &b); long long w = 0; // Undo cuts covered by the current one. while (s.size() > 1 && s.top().IsAbove(a, d, b)) { const Cut cut = s.top(); s.pop(); w -= cut.GetWeight(s.top(), sums); } // Add current cut. const Cut cut = s.top().SubCut(a, d, b); w += cut.GetWeight(s.top(), sums); s.push(cut); printf("%lld\n", w); } return 0; } |