#include <iostream> #include <algorithm> #include <vector> #include <cstdio> #include <queue> using std::vector; template<typename T> vector<T> readVect(int n) { vector<T> res; res.reserve(n); for (int i = 0; i < n; i++) { T a; std::cin >> a; res.push_back(a); } return res; } template <typename T> vector<size_t> sort_indexes(const vector<T> &v) { // initialize original index locations vector<size_t> idx(v.size()); iota(idx.begin(), idx.end(), 0); // sort indexes based on comparing values in v sort(idx.begin(), idx.end(), [&v](size_t i1, size_t i2) { return v[i1] < v[i2]; }); return idx; } void brutal(const vector<int64_t>& t, const vector<int>& d) { for (int j = 0; j < d.size(); j++) { int64_t minNextStart = 0; int64_t sum = 0; for (int i = 0; i < t.size(); i++) { int64_t wait = std::max(0ll, (minNextStart + d[j]) - t[i]); sum += wait; minNextStart = t[i] + wait; } std::cout << sum << "\n"; } } struct Group { int64_t t_beg; int count; int nextGroup; // sorry void append(Group& next) { count += next.count; nextGroup = next.nextGroup; if (next.count == 0) int aaa = 0; next.count = 0; // critical, sorry^2 } }; void brutal_inny(const vector<int64_t>& t, const vector<int>& d) { vector<int64_t> sums; sums.resize(d.size()); vector<Group> groups; groups.reserve(t.size() + 1); groups.push_back({0LL, 1, 1}); for (int i = 0; i < t.size(); i++) { groups.push_back({t[i], 1, groups.size() + 1}); } std::priority_queue< std::pair<int64_t, int> > pq; // pri + group index for (int i = 0; i < groups.size()-1; i++) { int64_t gap = groups[i + 1].t_beg - groups[i].t_beg; pq.push(std::make_pair(-gap, i)); } pq.push(std::make_pair(-1e18, -1)); int64_t d_mul = 0; int64_t sum_delta_tk = 0; // d * L*(L-1)/2 - sum_delta_tk; for (auto j : sort_indexes(d)) { auto dj = d[j]; while (-pq.top().first < dj) { int groupIndex = pq.top().second; pq.pop(); Group& ga = groups[groupIndex]; if (ga.count == 0) continue; // already merged Group& gb = groups[ga.nextGroup]; d_mul += ga.count * int64_t(gb.count); sum_delta_tk += (gb.t_beg - ga.t_beg) * gb.count; ga.append(gb); if (gb.nextGroup != groups.size()) { int64_t gap = groups[gb.nextGroup].t_beg - ga.t_beg; gap /= ga.count; // merged count pq.push(std::make_pair(-gap, groupIndex)); } } sums[j] = dj * d_mul - sum_delta_tk; } for (int j = 0; j < d.size(); j++) { std::cout << sums[j] << "\n"; } } int main() { std::ios_base::sync_with_stdio(0); // freopen("path", "r", stdin); int n, m; // 1 <= n, m <= 200 000 std::cin >> n >> m; vector<int64_t> t = readVect<int64_t>(n); // <= 10^12 vector<int> d = readVect<int>(m); // <= 10^6 // d = std::vector<int>(&d[0],&d[20]); // brutal(t, d); //std::cout << "---" <<std::endl; brutal_inny(t, d); }
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 131 | #include <iostream> #include <algorithm> #include <vector> #include <cstdio> #include <queue> using std::vector; template<typename T> vector<T> readVect(int n) { vector<T> res; res.reserve(n); for (int i = 0; i < n; i++) { T a; std::cin >> a; res.push_back(a); } return res; } template <typename T> vector<size_t> sort_indexes(const vector<T> &v) { // initialize original index locations vector<size_t> idx(v.size()); iota(idx.begin(), idx.end(), 0); // sort indexes based on comparing values in v sort(idx.begin(), idx.end(), [&v](size_t i1, size_t i2) { return v[i1] < v[i2]; }); return idx; } void brutal(const vector<int64_t>& t, const vector<int>& d) { for (int j = 0; j < d.size(); j++) { int64_t minNextStart = 0; int64_t sum = 0; for (int i = 0; i < t.size(); i++) { int64_t wait = std::max(0ll, (minNextStart + d[j]) - t[i]); sum += wait; minNextStart = t[i] + wait; } std::cout << sum << "\n"; } } struct Group { int64_t t_beg; int count; int nextGroup; // sorry void append(Group& next) { count += next.count; nextGroup = next.nextGroup; if (next.count == 0) int aaa = 0; next.count = 0; // critical, sorry^2 } }; void brutal_inny(const vector<int64_t>& t, const vector<int>& d) { vector<int64_t> sums; sums.resize(d.size()); vector<Group> groups; groups.reserve(t.size() + 1); groups.push_back({0LL, 1, 1}); for (int i = 0; i < t.size(); i++) { groups.push_back({t[i], 1, groups.size() + 1}); } std::priority_queue< std::pair<int64_t, int> > pq; // pri + group index for (int i = 0; i < groups.size()-1; i++) { int64_t gap = groups[i + 1].t_beg - groups[i].t_beg; pq.push(std::make_pair(-gap, i)); } pq.push(std::make_pair(-1e18, -1)); int64_t d_mul = 0; int64_t sum_delta_tk = 0; // d * L*(L-1)/2 - sum_delta_tk; for (auto j : sort_indexes(d)) { auto dj = d[j]; while (-pq.top().first < dj) { int groupIndex = pq.top().second; pq.pop(); Group& ga = groups[groupIndex]; if (ga.count == 0) continue; // already merged Group& gb = groups[ga.nextGroup]; d_mul += ga.count * int64_t(gb.count); sum_delta_tk += (gb.t_beg - ga.t_beg) * gb.count; ga.append(gb); if (gb.nextGroup != groups.size()) { int64_t gap = groups[gb.nextGroup].t_beg - ga.t_beg; gap /= ga.count; // merged count pq.push(std::make_pair(-gap, groupIndex)); } } sums[j] = dj * d_mul - sum_delta_tk; } for (int j = 0; j < d.size(); j++) { std::cout << sums[j] << "\n"; } } int main() { std::ios_base::sync_with_stdio(0); // freopen("path", "r", stdin); int n, m; // 1 <= n, m <= 200 000 std::cin >> n >> m; vector<int64_t> t = readVect<int64_t>(n); // <= 10^12 vector<int> d = readVect<int>(m); // <= 10^6 // d = std::vector<int>(&d[0],&d[20]); // brutal(t, d); //std::cout << "---" <<std::endl; brutal_inny(t, d); } |