#include <iomanip> #include <iostream> #include <utility> #include <algorithm> #include <cassert> #include <string> #include <vector> #include <set> #include <map> #include <numeric> using namespace std; #define ALL(x) x.begin(), x.end() #define VAR(a,b) __typeof (b) a = b #define IN(a) int a; cin >> a #define IN2(a,b) int a, b; cin >> a >> b #define REP(i,n) for (int _n=(n), i=0; i<_n; ++i) #define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i) #define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i) #define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i) #define PB push_back #define MP make_pair #define ST first #define ND second typedef vector<int> VI; typedef long long LL; typedef pair<int,int> PII; typedef double LD; /* CHECKLIST * 1) long longs * 2) lower_bound etc - out of bound * */ const int DBG = 0, INF = int(1e9); int n, m; vector<LL> a, sums; LL get_sum(LL beg, LL end) { LL res = sums[end]; if (0 != beg) res -= sums[beg - 1]; return res; } struct part { LL beg, end, day, val; part(LL beg_, LL end_, LL day_, LL val_) : beg(beg_), end(end_), day(day_), val(val_) {} }; std::ostream& operator<<(std::ostream &o, part p) { return o << "(beg = " << p.beg << ", end = " << p.end << ", day = " << p.day << ", val = " << p.val << ")"; } std::ostream& operator<<(std::ostream &o, const vector<part> &p) { FORE(it, p) o << *it << endl; return o; } bool is_cut(part p, LL k, LL day, LL cut_to) { LL cur_len = (day - p.day) * a[k] + p.val; return cur_len > cut_to; } part initial() { return part(0, n -1, 0, 0); } void read_area() { cin >> n >> m; a.resize(n); REP(i,n) cin >> a[i]; sort(ALL(a)); sums.resize(n); partial_sum(ALL(a), sums.begin()); } int main() { ios_base::sync_with_stdio(0); cout.setf(ios::fixed); read_area(); vector<part> parts(1, initial()); REP(q,m) { //cout << parts << endl << endl; LL day, cut_to; cin >> day >> cut_to; LL res = 0; while (!parts.empty()) { part p = parts.back(); parts.pop_back(); if (is_cut(p, p.beg, day, cut_to)) { //cout << "A\n"; LL len = p.end - p.beg + 1; res += len * p.val + get_sum(p.beg, p.end) * (day - p.day) - cut_to * len; } else if (!is_cut(p, p.end, day, cut_to)) { //cout << "B\n"; parts.PB(p); if (p.end < n - 1) parts.PB(part(p.end + 1, n - 1, day, cut_to)); break; } else { //cout << "C\n"; LL l = p.beg, r = p.end; while (l < r) { LL mid = (l + r) / 2; if (is_cut(p, mid, day, cut_to)) r = mid; else l = mid + 1; } part left(p.beg, l - 1, p.day, p.val); parts.PB(left); LL len = p.end - l + 1; res += len * p.val + get_sum(l, p.end) * (day - p.day) - cut_to * len; part right(l, n - 1, day, cut_to); parts.PB(right); break; } } if (parts.empty()) parts.PB(part(0, n - 1, day, cut_to)); cout << res << endl; } 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 125 126 127 | #include <iomanip> #include <iostream> #include <utility> #include <algorithm> #include <cassert> #include <string> #include <vector> #include <set> #include <map> #include <numeric> using namespace std; #define ALL(x) x.begin(), x.end() #define VAR(a,b) __typeof (b) a = b #define IN(a) int a; cin >> a #define IN2(a,b) int a, b; cin >> a >> b #define REP(i,n) for (int _n=(n), i=0; i<_n; ++i) #define FOR(i,a,b) for (int _b=(b), i=(a); i<=_b; ++i) #define FORD(i,a,b) for (int _b=(b), i=(a); i>=_b; --i) #define FORE(i,a) for (VAR(i,a.begin ()); i!=a.end (); ++i) #define PB push_back #define MP make_pair #define ST first #define ND second typedef vector<int> VI; typedef long long LL; typedef pair<int,int> PII; typedef double LD; /* CHECKLIST * 1) long longs * 2) lower_bound etc - out of bound * */ const int DBG = 0, INF = int(1e9); int n, m; vector<LL> a, sums; LL get_sum(LL beg, LL end) { LL res = sums[end]; if (0 != beg) res -= sums[beg - 1]; return res; } struct part { LL beg, end, day, val; part(LL beg_, LL end_, LL day_, LL val_) : beg(beg_), end(end_), day(day_), val(val_) {} }; std::ostream& operator<<(std::ostream &o, part p) { return o << "(beg = " << p.beg << ", end = " << p.end << ", day = " << p.day << ", val = " << p.val << ")"; } std::ostream& operator<<(std::ostream &o, const vector<part> &p) { FORE(it, p) o << *it << endl; return o; } bool is_cut(part p, LL k, LL day, LL cut_to) { LL cur_len = (day - p.day) * a[k] + p.val; return cur_len > cut_to; } part initial() { return part(0, n -1, 0, 0); } void read_area() { cin >> n >> m; a.resize(n); REP(i,n) cin >> a[i]; sort(ALL(a)); sums.resize(n); partial_sum(ALL(a), sums.begin()); } int main() { ios_base::sync_with_stdio(0); cout.setf(ios::fixed); read_area(); vector<part> parts(1, initial()); REP(q,m) { //cout << parts << endl << endl; LL day, cut_to; cin >> day >> cut_to; LL res = 0; while (!parts.empty()) { part p = parts.back(); parts.pop_back(); if (is_cut(p, p.beg, day, cut_to)) { //cout << "A\n"; LL len = p.end - p.beg + 1; res += len * p.val + get_sum(p.beg, p.end) * (day - p.day) - cut_to * len; } else if (!is_cut(p, p.end, day, cut_to)) { //cout << "B\n"; parts.PB(p); if (p.end < n - 1) parts.PB(part(p.end + 1, n - 1, day, cut_to)); break; } else { //cout << "C\n"; LL l = p.beg, r = p.end; while (l < r) { LL mid = (l + r) / 2; if (is_cut(p, mid, day, cut_to)) r = mid; else l = mid + 1; } part left(p.beg, l - 1, p.day, p.val); parts.PB(left); LL len = p.end - l + 1; res += len * p.val + get_sum(l, p.end) * (day - p.day) - cut_to * len; part right(l, n - 1, day, cut_to); parts.PB(right); break; } } if (parts.empty()) parts.PB(part(0, n - 1, day, cut_to)); cout << res << endl; } return 0; } |