Очень большая часть времени сегодняшнего контеста была потрачена мной на попытки сделать моё решение задачи E быстрее, несмотря на то, что оно должно иметь сложность O($$${n^2}logn$$$), которая при n <= 5000 должна проходить за 3 секунды. Единственное, что мне помогло, это изменение long long на int, но даже так оно осталось очень медленным. Есть ли у кого-то идеи почему моё решение задачи E такое медленное (снизу финальный код)? И подобный вопрос про задачу D, потому что я не вижу ни одной причины почему оно такое медленное:
Извините за внешний вид кода в решении E, я не знаю почему он сместился, потому что когда он отправлялся всё было в порядке.
I think in problem D it was better to use an unordered map.
Unordered map can cause your code to give TLE due to antihashing tests (O(n) instead of O(1)). Yes, it is possible to use unordered_map without worrying about it, but I hadn't the prewritten code needed for it
In problem E: You use ordered_set which is slow, you can use Fenwick tree
I thought that it should be pretty fast. I suppose it has a large constant then? Because the complexity of all operations of ordered_set should be O(logn)
E can be solved in O(n^2), checking every k from n to 1 in O(n).
D is solvable with zipped/global array with faster: 255734995
E is solvable with difference array in $$$O(n^2)$$$: 255678366
Oh, well, yeah, these are pretty smart optimizations, and I didn't think about them at first. Thank you!
Fallen C :(
Use a Fenwick Tree instead of an ordered set for E. Ordered set has a pretty high constant factor, which (I'm assuming) is why you TLE'd.
Actually, you do not need neither ordered set nor fenwick tree. Look at this.
Oh this is a nice approach. Definitely cleaner than abusing a Fenwick tree on this problem like I did.
D: Use array size of $$$ 10^{6}$$$ ,to clean array just do for with in $$$O(n+m)$$$
E: simple scanline
The code is shifted, because for indentation you use spaces and tabs interchangeably, and length of tabs in you IDE and on Codeforces is not the same. Better set in your IDE "always use spaces for indentation".
I never used tabs in my IDE, the only thing I've done with this particular code whas editing inside the codeforces send code window.. Maybe this added them