EDIT: Solved. It was not a problem with data structures, it was a logical error. I've been doing this greedy problem, and my solution fails on test case 6. For small inputs it seems to work, but for large inputs it produces strange results.
Problem: 854C - Вопросы планирования
My Solution: https://pastebin.com/MQBNBHEJ
Someone else's accepted solution: 30195313 — They used a priority_queue while I used a sorted vector. This should achieve the same result, and I do not think it is the data structure that is the problem.
Any idea what the problem might be?
Priority queue always keeps the elements in sorted order and accessing the maximum/minimum element takes
O(1)complexity and then rearranges itself inO(logn). So, basically you can access max/min inO(logn)in priority queue which is required to pass all the test cases. On the other hand if you are using vector you will have to sort it every time, each sorting takesO(nlogn). For n queries it will beO(n^2logn)which causes TLE.You can see my submission I have used
setto keep elements sorted.I can't see your solution