Traffic Lights CSES TLE

Problems and Contests
#1

Hi,

I tried to solve this problem and got TLE for the following solution:

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <string>
#include <climits>

using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int len, n;
	cin>>len>>n;

	set <int> lightPosition;
	lightPosition.insert(0);
	lightPosition.insert(len);
	map <int,int> longestPassage;
	longestPassage[len]=1;

	int x;
	for(int i=0; i<n; ++i){
		cin>>x;
		auto it = upper_bound(lightPosition.begin(), lightPosition.end(),x);
		int upper = (*it);
		it--;
		int lower = (*it);
		longestPassage[upper-lower]--;
		if(longestPassage[upper-lower] == 0){
			longestPassage.erase(upper-lower);
		}
		longestPassage[x-lower]++; longestPassage[upper-x]++;
		lightPosition.insert(x);
		auto ans = longestPassage.rbegin();
		cout<<(*ans).first<<" ";
	}

}

I believe my approach is similar to solution 1 [Solution - Traffic Lights (CSES)]. Could you help me figure out the reason of TLE

Also saw the second approach of processing lights in reverse order. How does this approach reduce time complexity?

Thanks

#2

Check the warning here: More Operations on Sorted Sets