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 #include #include #include #include #include const int OVENS = 200000; const int PEOPLE = 200000; class Safety : public std::pair { public: Safety(int x, int y) : std::pair(x, y) {} int safety() const { return first; } int& safety() { return first; } int index() const { return second; } }; int main() { std::ios::sync_with_stdio(0); int people_num, ovens_num; std::cin >> people_num >> ovens_num; std::vector t(people_num); for (int i = 0; i < people_num; i++) { std::cin >> t[i]; } std::vector safety(people_num); safety[0] = t[0]; for (int i = 1; i < people_num; i++) { safety[i] = t[i] - t[i - 1]; } std::vector> ovens(ovens_num); for (int i = 0; i < ovens_num; i++) { std::cin >> ovens[i].first; ovens[i].second = i; } std::sort(ovens.begin(), ovens.end()); for (int i = 0; i < ovens_num; i++) { //std::cout << "Oven: time = " << ovens[i].first << " | index = " << ovens[i].second << std::endl; } int current_global_delay = 0; std::set tagged_s; std::set waiting; std::vector waiting_time(people_num); std::vector result(ovens_num); // Computation for (int i = 0; i < people_num; i++) { tagged_s.emplace(safety[i], i); } for (int i = 0; i < ovens_num; i++) { //std::cout << "Considering oven with time " << ovens[i].first << std::endl; int oven_no = ovens[i].second; if (i > 0) { result[oven_no] = result[ovens[i - 1].second]; } int delta = ovens[i].first - current_global_delay; current_global_delay += delta; //std::cout << "Delta: " << delta << std::endl; // Every customer that was waiting waits now delta more. result[oven_no] += delta * waiting.size(); // Seeing if there's a new customer that needs to wait. while (tagged_s.size() > 0 && tagged_s.begin()->safety() < current_global_delay) { /* We have a new one that needs to wait */ Safety s = *tagged_s.begin(); tagged_s.erase(tagged_s.begin()); waiting.insert(s.index()); int s_waiting = current_global_delay - s.safety(); waiting_time[s.index()] = s_waiting; //std::cout << "Waiting time for " << s.index() << " is " << s_waiting << " for oven " << ovens[i].first << std::endl; result[oven_no] += s_waiting; /* If there's a new guy waiting, we need to change the safety of someone * else */ if (s.index() + 1 < people_num) { auto buddy = tagged_s.find(Safety(safety[s.index() + 1], s.index() + 1)); Safety buddy_safety = *buddy; tagged_s.erase(buddy); buddy_safety.safety() -= s_waiting; tagged_s.insert(buddy_safety); } } } for (int i = 0; i < ovens_num; i++) { std::cout << result[i] << std::endl; } return 0; }