#include <vector> #include <iostream> #include <algorithm> //#define DEBUG_LOGGING #ifdef DEBUG_LOGGING #include <stdio.h> #include <assert.h> #endif using namespace std; struct Cut { Cut(int pos, long long time, long long height) : pos(pos), time(time), height(height) {} bool operator<(const Cut &rhs) const { return pos < rhs.pos; } int pos; long long time, height; }; int main() { std::ios_base::sync_with_stdio(false); int field_size, cut_counts; cin >> field_size >> cut_counts; vector<int> speeds(field_size); for(int n = 0; n < field_size; n++) cin >> speeds[n]; std::sort(speeds.begin(), speeds.end()); vector<long long> speed_sums(field_size + 1); speed_sums.back() = 0; for(int n = field_size - 1; n >= 0; n--) speed_sums[n] = speed_sums[n + 1] + speeds[n]; vector<Cut> cuts; cuts.push_back(Cut(0, 0, 0)); #ifdef DEBUG_LOGGING printf("Sums: "); for(int n = 0; n < (int)speeds.size(); n++) printf("%d ", speeds[n]); printf("\n"); #endif long long time = 0; vector<long long> field(field_size, 0ll); for(int c = 0; c < cut_counts; c++) { long long cur_time, cut_height; cin >> cur_time >> cut_height; #ifdef DEBUG_LOGGING printf("cut: %lld %lld\n", cur_time, cut_height); #endif long long sum = 0; int new_pos = 0, last_pos = field_size; while(!cuts.empty()) { const Cut &last_cut = cuts.back(); int min_pos = last_cut.pos, max_pos = last_pos; long long growth_time = cur_time - last_cut.time; if(last_cut.height + growth_time * speeds[last_pos - 1] <= cut_height) break; while(min_pos < max_pos) { int mid_pos = (min_pos + max_pos) / 2; long long height = last_cut.height + growth_time * speeds[mid_pos]; #ifdef DEBUG_LOGGING printf("mid: %d (%lld)\n", mid_pos, height); #endif if(height >= cut_height) max_pos = mid_pos; else min_pos = mid_pos + 1; } if(min_pos == last_pos) break; #ifdef DEBUG_LOGGING printf("prev cut: %d %lld %lld | min: %d last: %d\n", last_cut.pos, last_cut.time, last_cut.height, min_pos, last_pos); printf("growth: %lld * %lld\n", growth_time, (speed_sums[min_pos] - speed_sums[last_pos])); #endif sum += growth_time * (speed_sums[min_pos] - speed_sums[last_pos]); sum += last_cut.height * (last_pos - min_pos); sum -= cut_height * (last_pos - min_pos); last_pos = min_pos; if(min_pos == last_cut.pos) cuts.pop_back(); else break; } if(last_pos < 0) last_pos = 0; if(last_pos < field_size) cuts.push_back(Cut(last_pos, cur_time, cut_height)); #ifdef DEBUG_LOGGING long long slow_sum = 0; { long long growth_mul = cur_time - time; time = cur_time; for(int n = 0; n < field_size; n++) { long long height = field[n] + growth_mul * speeds[n]; if(height > cut_height) { slow_sum += height - cut_height; height = cut_height; } field[n] = height; } } printf("sum: %lld slow: %lld\n", sum, slow_sum); assert(sum == slow_sum); #endif cout << sum << 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 128 129 130 | #include <vector> #include <iostream> #include <algorithm> //#define DEBUG_LOGGING #ifdef DEBUG_LOGGING #include <stdio.h> #include <assert.h> #endif using namespace std; struct Cut { Cut(int pos, long long time, long long height) : pos(pos), time(time), height(height) {} bool operator<(const Cut &rhs) const { return pos < rhs.pos; } int pos; long long time, height; }; int main() { std::ios_base::sync_with_stdio(false); int field_size, cut_counts; cin >> field_size >> cut_counts; vector<int> speeds(field_size); for(int n = 0; n < field_size; n++) cin >> speeds[n]; std::sort(speeds.begin(), speeds.end()); vector<long long> speed_sums(field_size + 1); speed_sums.back() = 0; for(int n = field_size - 1; n >= 0; n--) speed_sums[n] = speed_sums[n + 1] + speeds[n]; vector<Cut> cuts; cuts.push_back(Cut(0, 0, 0)); #ifdef DEBUG_LOGGING printf("Sums: "); for(int n = 0; n < (int)speeds.size(); n++) printf("%d ", speeds[n]); printf("\n"); #endif long long time = 0; vector<long long> field(field_size, 0ll); for(int c = 0; c < cut_counts; c++) { long long cur_time, cut_height; cin >> cur_time >> cut_height; #ifdef DEBUG_LOGGING printf("cut: %lld %lld\n", cur_time, cut_height); #endif long long sum = 0; int new_pos = 0, last_pos = field_size; while(!cuts.empty()) { const Cut &last_cut = cuts.back(); int min_pos = last_cut.pos, max_pos = last_pos; long long growth_time = cur_time - last_cut.time; if(last_cut.height + growth_time * speeds[last_pos - 1] <= cut_height) break; while(min_pos < max_pos) { int mid_pos = (min_pos + max_pos) / 2; long long height = last_cut.height + growth_time * speeds[mid_pos]; #ifdef DEBUG_LOGGING printf("mid: %d (%lld)\n", mid_pos, height); #endif if(height >= cut_height) max_pos = mid_pos; else min_pos = mid_pos + 1; } if(min_pos == last_pos) break; #ifdef DEBUG_LOGGING printf("prev cut: %d %lld %lld | min: %d last: %d\n", last_cut.pos, last_cut.time, last_cut.height, min_pos, last_pos); printf("growth: %lld * %lld\n", growth_time, (speed_sums[min_pos] - speed_sums[last_pos])); #endif sum += growth_time * (speed_sums[min_pos] - speed_sums[last_pos]); sum += last_cut.height * (last_pos - min_pos); sum -= cut_height * (last_pos - min_pos); last_pos = min_pos; if(min_pos == last_cut.pos) cuts.pop_back(); else break; } if(last_pos < 0) last_pos = 0; if(last_pos < field_size) cuts.push_back(Cut(last_pos, cur_time, cut_height)); #ifdef DEBUG_LOGGING long long slow_sum = 0; { long long growth_mul = cur_time - time; time = cur_time; for(int n = 0; n < field_size; n++) { long long height = field[n] + growth_mul * speeds[n]; if(height > cut_height) { slow_sum += height - cut_height; height = cut_height; } field[n] = height; } } printf("sum: %lld slow: %lld\n", sum, slow_sum); assert(sum == slow_sum); #endif cout << sum << endl; } return 0; } |