#include<cstdio> #include<list> #include<queue> #include<algorithm> #include<utility> using namespace std; long long speed[500000]; long long total[500000]; long long t; bool would_not_touch(long long speed, long long height) { long long area_height = speed * t; return area_height <= height; } int main(void) { int cuts; int areas; scanf("%d %d", &areas, &cuts); for (int i = 0; i < areas; i++) { scanf("%lld", &speed[i]); } sort(speed, speed + areas); for (int i = 0; i < areas; i++) { total[i] = speed[i] + (i == 0 ? 0 : total[i-1]); } long long cut = 0; for (int i = 0; i < cuts; i++) { long long day, height; scanf("%lld %lld", &day, &height); t = day; long long* first_cut = lower_bound(speed, speed + areas, height, would_not_touch); int cut_idx = first_cut - speed; long long to_cut = -cut; to_cut += (total[areas-1] - (cut_idx == 0 ? 0 : total[cut_idx-1])) * day; to_cut -= (areas - cut_idx) * height; to_cut = max(0LL, to_cut); cut += to_cut; printf("%lld\n", to_cut); } 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 | #include<cstdio> #include<list> #include<queue> #include<algorithm> #include<utility> using namespace std; long long speed[500000]; long long total[500000]; long long t; bool would_not_touch(long long speed, long long height) { long long area_height = speed * t; return area_height <= height; } int main(void) { int cuts; int areas; scanf("%d %d", &areas, &cuts); for (int i = 0; i < areas; i++) { scanf("%lld", &speed[i]); } sort(speed, speed + areas); for (int i = 0; i < areas; i++) { total[i] = speed[i] + (i == 0 ? 0 : total[i-1]); } long long cut = 0; for (int i = 0; i < cuts; i++) { long long day, height; scanf("%lld %lld", &day, &height); t = day; long long* first_cut = lower_bound(speed, speed + areas, height, would_not_touch); int cut_idx = first_cut - speed; long long to_cut = -cut; to_cut += (total[areas-1] - (cut_idx == 0 ? 0 : total[cut_idx-1])) * day; to_cut -= (areas - cut_idx) * height; to_cut = max(0LL, to_cut); cut += to_cut; printf("%lld\n", to_cut); } return 0; } |