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. Explanation of my approach is on comments.

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: Let's call pair $$$(i, j)$$$ bad if $$$i < j$$$ and $$$a_i > a_j$$$. We need to find if maximum sum of bad pars, which is inside $$$[l_i, r_i]$$$, is not greater than $$$k$$$ (for all bad $$$(i, j)$$$ satisfies $$$a_i + a_j \le k$$$).

Create a segment tree for maximum value and a merge sort tree where each node has a sorted vector containing all elements in the range of this node. Store the maximum sum of bad pair, which is inside $$$[l_{node},r_{node}]$$$, in $$$vis_{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 $$$true$$$. If its entirely contained, first we check if $$$vis_{node} \le k$$$, if so we can do binary search on the vector to find the greatest element which is smaller than $$$mx$$$ (max number before this segment($$$node$$$)) to find maximum sum of bad pairs which right element is in $$$[l_{node},r_{node}]$$$ and left element is in $$$[l_i, l_{node} - 1]$$$. And check $$$mx + element \le k$$$ then update $$$mx$$$. If neither of the previous conditions are satisfied, we take the answer of the left child and the answer of the right child. Check if they are both $$$true$$$. 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)$$$.

Unrelated: Did you find a VPN for oj.uz in Turkmenistan?

Not VPN, TOR browser with bridge.