traffic_lights.cpp (802B)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 using ui = unsigned int; 6 using l = long; 7 using ul = unsigned long; 8 using ll = long long; 9 using ull = unsigned long long; 10 11 using vi = vector<int>; 12 using vui = vector<ui>; 13 using vl = vector<l>; 14 using vul = vector<ul>; 15 using vll = vector<ll>; 16 using vull = vector<ull>; 17 18 void solve() 19 { 20 int x, n; 21 cin >> x >> n; 22 int res = x; 23 set<int> lights = { 0, x }; 24 multiset<int> dists = { x }; 25 int tmp; 26 for (int i = 0; i < n; i++) { 27 cin >> tmp; 28 29 auto it = lights.upper_bound(tmp); 30 auto it2 = it; 31 it2--; 32 33 dists.erase(dists.find(*it - *it2)); 34 dists.insert(tmp - *it2); 35 dists.insert(*it - tmp); 36 lights.insert(tmp); 37 38 it = dists.end(); 39 --it; 40 cout << *it << " "; 41 } 42 cout << "\n"; 43 } 44 45 int main() 46 { 47 ios::sync_with_stdio(0); 48 cin.tie(0); 49 solve(); 50 }