#define DBG false #include <iostream> #include <algorithm> #include <stack> using namespace std; int n, m; int speeds[500000]; long long accumulated[500000]; void read_and_sort_speeds() { for (int i = 0; i < n; ++i) { cin >> speeds[i]; } // desc sort sort(speeds, speeds + n, [](int a, int b){return a > b;}); } void compute_accumulated() { accumulated[0] = speeds[0]; for (int i = 1; i < n; ++i) { accumulated[i] = accumulated[i-1] + speeds[i]; if (DBG) { cout << "acc[" << i << "]: " << accumulated[i] << endl; } } } struct cut { cut(long long d, long long b, int end): d(d), b(b), end(end) {} const long long d; const long long b; const int end; }; ostream& operator<<(ostream& os, const cut& c) { return os << "cut(" << c.d << ", " << c.b << ", " << c.end << ")"; } stack<cut> cuts; int find_first_not_cut(long long d, int begin, const cut& c, long long b) { long long days = d - c.d; int* bound = upper_bound(speeds + begin, speeds + c.end, b, [days, &c](long long b, int speed) { return days * speed + c.b < b; }); int result = bound - speeds; if (DBG) { cout << "last cut: " << d << ", " << begin << ", " << c << ", " << b << " -> " << result << endl; } return result; } long long cut_area(long long d, int begin, int end, const cut& c, long long b) { if (begin >= end) { return 0; } long long days = d - c.d; long long one_day = accumulated[end - 1]; if (begin > 0) { one_day -= accumulated[begin - 0]; } long long result = days * one_day; if (DBG) { cout << "cut_area " << d << ", " << begin << ", " << end << ", " << c << ", " << b << endl; cout << "one day: " << one_day << ", tmp: " << result << endl; } long long rect = (long long)(end - begin) * (b - c.b); if (DBG) { cout << "rect: " << rect << endl; } return result - rect; } void compute() { for (int i = 0; i < m; ++i) { long long area = 0; long long d, b; cin >> d >> b; int first_not_cut = 0; while (!cuts.empty()) { if (DBG) { cout << "while.. d: " << d << ", " << b << ", top: " << cuts.top() << endl; } int next_first_not_cut = find_first_not_cut(d, first_not_cut, cuts.top(), b); // TODO compute area area += cut_area(d, first_not_cut, next_first_not_cut, cuts.top(), b); // first_not_cut = next_first_not_cut; if (first_not_cut == cuts.top().end) { if (DBG) cout << "pop" << endl; cuts.pop(); } else { if (DBG) cout << "break\n"; break; } } if (DBG) { cout << "cuts.empty(): " << cuts.empty() << ", area: " << area << ", first_not_cut: " << first_not_cut << endl; } if (area > 0) { cuts.push(cut(d, b, first_not_cut)); } cout << area << endl; } } int main() { cin >> n >> m; read_and_sort_speeds(); compute_accumulated(); cuts.push(cut(0, 0, n)); compute(); 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 | #define DBG false #include <iostream> #include <algorithm> #include <stack> using namespace std; int n, m; int speeds[500000]; long long accumulated[500000]; void read_and_sort_speeds() { for (int i = 0; i < n; ++i) { cin >> speeds[i]; } // desc sort sort(speeds, speeds + n, [](int a, int b){return a > b;}); } void compute_accumulated() { accumulated[0] = speeds[0]; for (int i = 1; i < n; ++i) { accumulated[i] = accumulated[i-1] + speeds[i]; if (DBG) { cout << "acc[" << i << "]: " << accumulated[i] << endl; } } } struct cut { cut(long long d, long long b, int end): d(d), b(b), end(end) {} const long long d; const long long b; const int end; }; ostream& operator<<(ostream& os, const cut& c) { return os << "cut(" << c.d << ", " << c.b << ", " << c.end << ")"; } stack<cut> cuts; int find_first_not_cut(long long d, int begin, const cut& c, long long b) { long long days = d - c.d; int* bound = upper_bound(speeds + begin, speeds + c.end, b, [days, &c](long long b, int speed) { return days * speed + c.b < b; }); int result = bound - speeds; if (DBG) { cout << "last cut: " << d << ", " << begin << ", " << c << ", " << b << " -> " << result << endl; } return result; } long long cut_area(long long d, int begin, int end, const cut& c, long long b) { if (begin >= end) { return 0; } long long days = d - c.d; long long one_day = accumulated[end - 1]; if (begin > 0) { one_day -= accumulated[begin - 0]; } long long result = days * one_day; if (DBG) { cout << "cut_area " << d << ", " << begin << ", " << end << ", " << c << ", " << b << endl; cout << "one day: " << one_day << ", tmp: " << result << endl; } long long rect = (long long)(end - begin) * (b - c.b); if (DBG) { cout << "rect: " << rect << endl; } return result - rect; } void compute() { for (int i = 0; i < m; ++i) { long long area = 0; long long d, b; cin >> d >> b; int first_not_cut = 0; while (!cuts.empty()) { if (DBG) { cout << "while.. d: " << d << ", " << b << ", top: " << cuts.top() << endl; } int next_first_not_cut = find_first_not_cut(d, first_not_cut, cuts.top(), b); // TODO compute area area += cut_area(d, first_not_cut, next_first_not_cut, cuts.top(), b); // first_not_cut = next_first_not_cut; if (first_not_cut == cuts.top().end) { if (DBG) cout << "pop" << endl; cuts.pop(); } else { if (DBG) cout << "break\n"; break; } } if (DBG) { cout << "cuts.empty(): " << cuts.empty() << ", area: " << area << ", first_not_cut: " << first_not_cut << endl; } if (area > 0) { cuts.push(cut(d, b, first_not_cut)); } cout << area << endl; } } int main() { cin >> n >> m; read_and_sort_speeds(); compute_accumulated(); cuts.push(cut(0, 0, n)); compute(); return 0; } |