#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; typedef pair<int,int> pii; struct Grass { ll height, cm_per_day, last_cut; Grass() : height(0LL), cm_per_day(0LL), last_cut(0LL) {} // Grass(int _cm_per_day) : cm_per_day(_cm_per_day) {} // Grass(int _height, int _cm_per_day) : height(_height), cm_per_day(_cm_per_day) {} }; bool operator<(Grass a, Grass b) { return a.cm_per_day < b.cm_per_day; } vector<Grass> ares; queue<pii> Q; int find_cut_point(int d, int b) { int beg = 0, end = ares.size()-1, middle; while(beg < end) { middle = (beg+end)/2; ares[middle].height += ares[middle].cm_per_day * (d - ares[middle].last_cut); ares[middle].last_cut = d; if(ares[middle].height >= b) end = middle; else beg = middle+1; } middle = (beg+end)/2; return middle; } int main() { int n,m; scanf("%d%d", &n, &m); ares.resize(n); for(int i = 0; i < n; i++) scanf("%lld", &ares[i].cm_per_day); sort(ares.begin(), ares.end()); // for(int i = 0; i < n; i++) // printf("%lld ", ares[i].cm_per_day); ll in_d, in_b; for(int i = 0; i < m; i++) { scanf("%lld%lld", &in_d, &in_b); Q.push(pii(in_d, in_b)); } while(!Q.empty()) { ll sum = 0LL, d = Q.front().first, b = Q.front().second; Q.pop(); // find first element that is being cut down int interception = find_cut_point(d, b); // printf("cut time: (%lld %lld) %d\n", d, b, interception); for(int i = interception; i < n; i++) { ares[i].height += ares[i].cm_per_day * (d - ares[i].last_cut); if(ares[i].height > b) { sum += ares[i].height - b; ares[i].height = b; } ares[i].last_cut = d; } printf("%lld\n", sum); } 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 <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; typedef pair<int,int> pii; struct Grass { ll height, cm_per_day, last_cut; Grass() : height(0LL), cm_per_day(0LL), last_cut(0LL) {} // Grass(int _cm_per_day) : cm_per_day(_cm_per_day) {} // Grass(int _height, int _cm_per_day) : height(_height), cm_per_day(_cm_per_day) {} }; bool operator<(Grass a, Grass b) { return a.cm_per_day < b.cm_per_day; } vector<Grass> ares; queue<pii> Q; int find_cut_point(int d, int b) { int beg = 0, end = ares.size()-1, middle; while(beg < end) { middle = (beg+end)/2; ares[middle].height += ares[middle].cm_per_day * (d - ares[middle].last_cut); ares[middle].last_cut = d; if(ares[middle].height >= b) end = middle; else beg = middle+1; } middle = (beg+end)/2; return middle; } int main() { int n,m; scanf("%d%d", &n, &m); ares.resize(n); for(int i = 0; i < n; i++) scanf("%lld", &ares[i].cm_per_day); sort(ares.begin(), ares.end()); // for(int i = 0; i < n; i++) // printf("%lld ", ares[i].cm_per_day); ll in_d, in_b; for(int i = 0; i < m; i++) { scanf("%lld%lld", &in_d, &in_b); Q.push(pii(in_d, in_b)); } while(!Q.empty()) { ll sum = 0LL, d = Q.front().first, b = Q.front().second; Q.pop(); // find first element that is being cut down int interception = find_cut_point(d, b); // printf("cut time: (%lld %lld) %d\n", d, b, interception); for(int i = interception; i < n; i++) { ares[i].height += ares[i].cm_per_day * (d - ares[i].last_cut); if(ares[i].height > b) { sum += ares[i].height - b; ares[i].height = b; } ares[i].last_cut = d; } printf("%lld\n", sum); } return 0; } |