I'll assume you read the editorial for F but could not understand that solution, so I'll go ahead and try to explain another approach.

For each position i, we need to know how many times that position was modified by the operation. For queries of type 1, we get an interval [l, r] and we need to apply the operation on every position i from l to r. But how do we do that?

We could have an array initially filled with zeros to maintain a counter of how many operations were done for each position. Say, for n=5, this array would start as [0, 0, 0, 0, 0], and if we got a query of type 1 in the interval [3, 5], our array would update to [0, 0, 1, 1, 1], as we did one operation on positions 3, 4, and 5.

Now, a simple way to maintain this operation counter array would be to iterate over each position from l to r, whenever we receive a query of type 1, and add 1 to each position. But straightforwardly doing that would TLE, as it would take O(n) (linear time) to process each query of type 1.

But what if we could do this update operation on our array of counters in O(logn)? That is where the data structure BIT (Binary Indexed Tree, or Fenwick Tree) comes in handy. We can do range updates (say, add 1 to each position from l to r) in O(logn). If this is your first time hearing about this data structure, I suggest you read a bit more about it. It can be a bit daunting to understand at first, but the code is really easy.

Well, now that we can process queries of type 1 in O(logn) time, now we're left with queries of type 2. To process those, we only need to read the value present in our array of counter, for the requested position. After reading this value, we can apply the operation in a straightforward manner, as it is really fast.

Here is my submission to make more sense of what I tried to explain. Please let me know if you have any more questions and I'll try my best to answer them.

Yup! I did.

Because it is possible to find answers for odd values of n.

For example, for n = 5, we could answer [-1, 2, -1, 2, -1]

Thank you so much for the explanation!

I was trying to solve the problem using a really similar logic (ie. trying to sort the array in a "greedy" way, fixing the first position, then the second, then the third... until the (n-2)th position. But I was missing the "if we ever have a repeat element then we can always sort it." part. Reading your comment made me realise that.

Following this same logic, I'm still trying to figure out the reason we can always sort the sequence if there are any duplicates. One of the reasons I could think of was that by the end of the operations we end up with the last elements being something like "x y x" in which x < y. So in this case, even if the first x is in its correct position, we still need to apply a shift, to get "x x y". That being said, this reason is not sufficient, as can be seen in this commit (see line 91).

3 years late but here I am, in case anyone has the same question. If you try to draw this test case (a line with the segments covering their respective spaces), you'll see the segment [1, 2) of the line would be uncovered if you were to remove the TV [1, 3], for example. As the size of the range [1, 2) is not 1 (**not an integer**), we can safely remove it and the answer would be valid. The same would happen if we were to remove segment [5, 7], as it would uncover (6, 7], so it would also be a valid answer

It is not against the rules if the idea is that someone explains the problems to you after the contest.

I hope you can find someone to help you! Good luck!

Not entering the matter of whether that kind of post "feels good" or not but, well... If you don't like it, you can just skip the post (or downvote it, if you might). Not every single post needs to please everyone and that is normal in our community

sorry my response is 10 months late :p

I was solving this question today and had a problem similar to yours. You probably forgot to sort all Ai's and Bi's (that was my mistake)

In my DP, if we don't sort all Ai's and Bi's, the transition between states won't cover all needed cases to find the best possible time. Reason for that is, you could, for a person i, ignore key j and try to get solve(i, j+1) as an answer. But the state (i, j+1) wouldn't consider the previously ignored key j as an option for all persons with index greater than i, and we have no guarantee that it wouldn't be a "good choice" for other person with index greater than i

By sorting both arrays A and B we guarantee that if person i ignores key j in (i, j) state, it would not make sense for another person with index greater than i consider that ignored key j as an option, because it would increase the answer. So we don't need to care about keys lesser j in state (i, j) anymore, and now our DP covers all needed cases to find best possible time

Up until now, people are only hacking their own solutions (the only solutions they can see right now).

I was hoping we would have something like this being applied today... :(