# CSES Traffic Lights Solution

Oct 23rd, 2021
1,003
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <set>
4. #include <algorithm>
5.
6. using std::cout;
7. using std::endl;
8. using std::vector;
9.
10. int main() {
11.     int street_len;
12.     int light_num;
13.     std::cin >> street_len >> light_num;
14.     vector<int> lights(light_num);
15.     for (int& l : lights) {
16.         std::cin >> l;
17.     }
18.     // Initialize the set with beginning and ending values
19.     std::set<int> street_pos{0, street_len};
20.     for (int l : lights) {
21.         street_pos.insert(l);
22.     }
23.
24.     vector<int> gaps(light_num);
25.     int prev = 0;
26.     int max_gap = 0;
27.     // Find the longest passage once all the streetlights are added
28.     for (int p : street_pos) {
29.         max_gap = std::max(max_gap, p - prev);
30.         prev = p;
31.     }
32.     gaps.back() = max_gap;
33.
34.     /*
35.      * Remove the streetlights in reverse order to how they were added, then find
36.      * the gap created by removing each. Find the biggest current gap, and
38.      */
39.     for (int i = light_num - 1; i > 0; i--) {
40.         street_pos.erase(lights[i]);
41.         auto high_it = street_pos.upper_bound(lights[i]);
42.         int high = *high_it;
43.         int low = *(--high_it);
44.         max_gap = std::max(max_gap, high - low);
45.         gaps[i - 1] = max_gap;
46.     }
47.
48.     for (int i = 0; i < gaps.size() - 1; i++) {
49.         cout << gaps[i] << ' ';
50.     }
51.     cout << gaps.back() << endl;
52. }
53.
RAW Paste Data