#include <cstdio> #include <list> #include <unordered_set> #include <algorithm> #include <cmath> using namespace std; const int MAX_COUNT = 200003; struct Oven { int time; int index; }; struct Group { int index_first; int index_last; }; bool ovenscomp(Oven a, Oven b) { return a.time < b.time; } inline long long int cumsum(int n) { if (n % 2 == 0) { return (long long int)n/2*(n+1); } else { return ((long long int)n+1)/2*n; } } bool should_extend(Group g, long long int* times, long long int* t_diffs, int n, int d) { if (g.index_last >= n) return false; int length = g.index_last - g.index_first; long long int t_prev = g.index_first > 0 ? times[g.index_first-1] : 0; if (length == 0) { return (long long int)d > t_diffs[g.index_last]; } return (length+1) * (long long int)d - (times[g.index_last-1] - t_prev) > t_diffs[g.index_last]; } long long int delay(Group g, long long int* times, long long int* partial_times, int d) { int length = g.index_last - g.index_first; if (length == 0) return 0; long long int t_prev = g.index_first > 0 ? times[g.index_first-1] : 0; return cumsum(length) * d - (partial_times[g.index_last] - partial_times[g.index_first]) + length * t_prev; } int n; //number of clients int m; //number of ovens long long int t[MAX_COUNT]; //times of clients arrival Oven ovens[MAX_COUNT]; //ovens baking time long long int min_diff; //minimal difference of times of clients arrival long long int t_diff[MAX_COUNT]; //differences of times of clients arrival long long int part_times[MAX_COUNT]; //partial sums of times of clients arrival Group groups[MAX_COUNT]; unordered_set<int> nonempty_groups; long long int results[MAX_COUNT]; //results for particular ovens int main(int argc, char *argv[]) { scanf("%d %d\n", &n, &m); for (int i = 0; i < n; i++) { scanf("%lld", &t[i]); } scanf("\n"); for (int i = 0; i < m; i++) { int ot; scanf("%d", &ot); ovens[i] = {ot, i}; } sort(ovens, ovens+m, ovenscomp); min_diff = t[0]; t_diff[0] = min_diff; for (int i = 1; i < n; i++) { t_diff[i] = t[i]-t[i-1]; if (t_diff[i] < min_diff) min_diff = t_diff[i]; } part_times[0] = 0; for (int i = 0; i < n; i++) { part_times[i+1] = part_times[i] + t[i]; } for (int i = 0; i <= n; i++) { groups[i] = {i, i}; } for (int c = 0; c < m; c++) { Oven d = ovens[c]; long long int total = 0; if (d.time > min_diff) { int j = 0; while (j < n) { Group g = groups[j]; if (should_extend(g, t, t_diff, n, d.time)) { //merging groups nonempty_groups.erase(g.index_last+1); nonempty_groups.insert(g.index_first); g.index_last = groups[g.index_last+1].index_last; groups[j] = g; } else { j = g.index_last+1; } } for (unordered_set<int>::iterator it = nonempty_groups.begin(); it != nonempty_groups.end(); it++) { total += delay(groups[*it], t, part_times, d.time); } } results[d.index] = total; } for (int c = 0; c < m; c++) { printf("%lld\n", results[c]); } 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 | #include <cstdio> #include <list> #include <unordered_set> #include <algorithm> #include <cmath> using namespace std; const int MAX_COUNT = 200003; struct Oven { int time; int index; }; struct Group { int index_first; int index_last; }; bool ovenscomp(Oven a, Oven b) { return a.time < b.time; } inline long long int cumsum(int n) { if (n % 2 == 0) { return (long long int)n/2*(n+1); } else { return ((long long int)n+1)/2*n; } } bool should_extend(Group g, long long int* times, long long int* t_diffs, int n, int d) { if (g.index_last >= n) return false; int length = g.index_last - g.index_first; long long int t_prev = g.index_first > 0 ? times[g.index_first-1] : 0; if (length == 0) { return (long long int)d > t_diffs[g.index_last]; } return (length+1) * (long long int)d - (times[g.index_last-1] - t_prev) > t_diffs[g.index_last]; } long long int delay(Group g, long long int* times, long long int* partial_times, int d) { int length = g.index_last - g.index_first; if (length == 0) return 0; long long int t_prev = g.index_first > 0 ? times[g.index_first-1] : 0; return cumsum(length) * d - (partial_times[g.index_last] - partial_times[g.index_first]) + length * t_prev; } int n; //number of clients int m; //number of ovens long long int t[MAX_COUNT]; //times of clients arrival Oven ovens[MAX_COUNT]; //ovens baking time long long int min_diff; //minimal difference of times of clients arrival long long int t_diff[MAX_COUNT]; //differences of times of clients arrival long long int part_times[MAX_COUNT]; //partial sums of times of clients arrival Group groups[MAX_COUNT]; unordered_set<int> nonempty_groups; long long int results[MAX_COUNT]; //results for particular ovens int main(int argc, char *argv[]) { scanf("%d %d\n", &n, &m); for (int i = 0; i < n; i++) { scanf("%lld", &t[i]); } scanf("\n"); for (int i = 0; i < m; i++) { int ot; scanf("%d", &ot); ovens[i] = {ot, i}; } sort(ovens, ovens+m, ovenscomp); min_diff = t[0]; t_diff[0] = min_diff; for (int i = 1; i < n; i++) { t_diff[i] = t[i]-t[i-1]; if (t_diff[i] < min_diff) min_diff = t_diff[i]; } part_times[0] = 0; for (int i = 0; i < n; i++) { part_times[i+1] = part_times[i] + t[i]; } for (int i = 0; i <= n; i++) { groups[i] = {i, i}; } for (int c = 0; c < m; c++) { Oven d = ovens[c]; long long int total = 0; if (d.time > min_diff) { int j = 0; while (j < n) { Group g = groups[j]; if (should_extend(g, t, t_diff, n, d.time)) { //merging groups nonempty_groups.erase(g.index_last+1); nonempty_groups.insert(g.index_first); g.index_last = groups[g.index_last+1].index_last; groups[j] = g; } else { j = g.index_last+1; } } for (unordered_set<int>::iterator it = nonempty_groups.begin(); it != nonempty_groups.end(); it++) { total += delay(groups[*it], t, part_times, d.time); } } results[d.index] = total; } for (int c = 0; c < m; c++) { printf("%lld\n", results[c]); } return 0; } |