I was trying to solve IZHO19_sortbooks on oj.uz. In problem $$$n, m <= 10^6$$$ and Time Limit is 3s.
I have 2 questions: Why I got full score? And why if I change code a bit or submit exactly the same code doesn't get the same result?
Time complexity of my solution is $$$O(n \cdot log_2(n) + m \cdot \log_2(n)^2)$$$ and memory usage is exactly $$$256$$$ MB($$$262 144$$$ KB). It should be $$$TLE$$$ because $$$10^6 \cdot \log_2(10^6)^2 = 397 267 425.6 > 3 \cdot 10^8$$$ and it's almost $$$MLE$$$ (if it used just $$$1$$$ KB more). What's more weird is if I change my code a bit it won't get full score because of $$$MLE$$$. Even if I submit a code again, it might not get the same result.
Following 2 codes are same but $$$1^{st}$$$ submission got $$$100$$$, $$$2^{nd}$$$ is $$$MLE$$$:
$$$1^{st}$$$ submission:1096192 got $$$100$$$ pts, $$$2^{nd}$$$ submission:1096203 got $$$77$$$ pts and it's $$$MLE$$$.
You can look my other submission too: link.
Could you explain your approach to solve the problem? That would make the code a little bit more understandable
Problem can be simplified like these: is $$$max(a_i, a_j) \le k$$$ which $$$l \le i < j \le r$$$ and $$$a_i > a_j$$$
Let's create a merge sort tree where each node has a sorted vector containing all elements in the range of this node. Now we can answer the query recursively like a segment tree. For some $$$node$$$ if $$$[l_node,r_node]$$$ is outside $$$[l_i,r_i]$$$ its answer is obviously $$$0$$$. If its entirely contained, we can do binary search on the vector to find how many elements satisfy the conditions. If neither of the previous conditions are satisfied, we take the answer of the right child + the answer of the left child. Time complexity for building the merge sort tree is $$$O(nlogn)$$$ because we go through each element $$$logn$$$ times, and the time complexity for answering the queries is $$$O(qlog^2n)$$$ because in each query we visit logn nodes at most, doing binary search in each one in $$$O(logn)$$$.