So I was stuck in this problem 2053B - Outstanding Impressionist for a long time; finally I am able to solve this problem a little while ago. I have used hashing technique to solve it. Firstly, let me explain how I have solved it. (If you do not want to hear me chattering about my solution approach, then skip the next two paragraphs.)

I have noticed that whenever l_i and r_i are equal, it is guaranteed that there is a w_i with the value of l_i (or r_i) exists in the impression. If the same equal value of l_i and r_i appear again, that means there must be multiple instances of the same value of w_i is present in the impression, which means the ith piece of the impression must not be unique; otherwise, it will be unique as all the other pieces can be set to different values other than that of w_i. An easy way to implement this logic would be to use hashing and store the frequency of those values of w_i such that l_i = r_i. If the frequency of w_i is greater than 1, then w_i is not unique; and if it is 1, then it is unique.

Now what happens when l_i and r_i are not equal? In that case, we have to check if there exists any v such that l_i ≤ v ≤ r_i and for any 1 ≤ j ≤ n if l_j = r_j, then v ≠ l_j. It is because if such v exists, then we can set all the values of the other pieces of impression not equal to v and set w_i to equal to v and hence, w_i will be unique. Now how to implement this logic? At first, I have stored every possible values of w_i in increasing order in a vector which are not guaranteed to be present in the impression. (Only when l_i = r_i, a piece of impression of the value w_i = l_i is guaranteed to be present in the impression.) I can do this by iterating from 1 to 2n and check whether the value is already present (or have frequency greater than 0) in the hash array/map which was previously created to store the frequency of w_i which was guaranteed to be present. It is possible because of the constraints 1 ≤ l_i ≤ r_i ≤ 2n and l_i ≤ w_i ≤ r_i and n ≤ 2.10⁵, which means to do this, I have to do at most 4.10⁵ operations since the largest value of r_i or w_i is 4.10⁵. After that, I have used binary search to look for the smallest value equal to or greater than l_i in the newly created vector (let this value be c) and checked if c is equal to or less than r_i or not. If c is equal to or less than r_i, then we can set the value of w_i to be c and the other pieces of impression to be not equal to c and hence, w_i will be unique. Otherwise, w_i will not be unique.

So this was all the logic and idea I came up with to solve the problem. At first, I implemented the hashing using unordered map and the verdict I received was TLE on testcase 12. Here is the submission 322353823. After receiving TLE, I thought since my code has time complexity of O(nlogn) for using binary search n times, I have to somehow get rid of this binary search and do the searching in constant time. But I did not know how to do so and ended up with the notion that my approach was not right. Then for some reason, I decided to implement the hashing using vector. I did it because I thought although unordered map takes constant time on average to insert and update its elements, a hash array created using vector also takes constant time to do the same and also not on average but always. After doing so, my solution got accepted 322354822. So today I have learned a new lesson that hash array created using vector is faster than unordered map. But my question is: Why is there a significant gap in performance between these two methods? Although unordered map is slower, shouldn't it also pass the testcases? Since the accepted solution takes 93 ms to pass the 12th testcase and the time limit is 1s, does that mean vector is more than 10 times faster compared to unordered map? And when the input is in 10⁶ range, should I always implement hashing using vector? When would using unordered map be appropriate? These are some questions that have arisen in my head. Any sort of help would be appreciated.