So here is the cses problem CSES - Traffic Lights
So after every new position, I can break the segment into two smaller segments and then calculate their lengths and repeat for all the inputs. Also use binary search to find where the new position will be, that is in which segment would it be added to.
What I am getting stuck at is the implementation part. Can someone please help me?
use 1 multiset to save the road after adding the traffic light
then use 1 set to save the position of the traffic light
u can delete the pragma , but remember to sync_with_stdio or u will get tle
#pragma GCC optimize(“Ofast”)
#include<bits/stdc++.h>
using namespace std;
multiset s; // luu cac quang duoc sau moi lan them den giao thong
set d ; // luu vi tri cac den giao thong
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
long long m, n ;
cin >> m >> n ;
s.insert(m) ;
d.insert(0) ;
d.insert(m) ;
long long x ;
while(n–)
{
cin >> x;
d.insert(x) ;
auto it = d.find(x) ;
long long previous = *prev(it) ;
long long behind = *next(it) ;
s.insert(x-previous);
s.insert(behind-x) ;
s.erase(s.find(behind-previous));
cout << *(s.rbegin())<< " ";
}
return 0;
}