SansPapyrus683

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
  37.      * add it to the next lowest index in answer.
  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