It sure does, at first it seemed solvable but as the time progressed (and 3 WAs) I started to give up. Hope it goes better for the others :)

It is a nice exercise to learn range DP and you can also learn it from the USACO guide.

I don't think using a queue or a deque matters, but rather the other parts of your code were probably the reason why you got a TLE.

I used Deque and MultiSet Both , Still passed way within Time Limit.

sorting part gives tl, you have to optimise it in some way

First of all , provide link to your code and don't paste it directly , and secondly sorting is the reason for TLE . Just think , first 10^5 operation of append and then 10^5 operation of sorting , Operation will be (10^10)*log(10^5)

I used Set and Queue and passed in time limit

I used a minheap for the prefix and a deque for the suffix.

• operation 1 -- add to suffix
• operation 2 -- pop from minheap if not empty, else popleft from suffix deque
• operation 3 -- pop everything from suffix and push to minheap

The time limit I think was generous to let us Pythonites in. I think that resorting after every operation 3 was intended to get TLE, but the relaxed python limits might have let that slide for C++.

What was the solution of G?

Yes, I also think that G seemed easier. Switched to it after I noticed that rainboy took less time to solve G than F. Still couldn't make it in time and only got a correct answer for the 2nd sample so far. Trying to upsolve it now.

You should have used Multiset

use multiset and queue

Maintain a queue of elements that are inserted and two sets (one for the sorted part and the other for the non-sorted part). When sorting query is applied, just use small to large merging and the rest two cases are pure implementation and case work in 3-4 lines.

EDIT: Small to large merging is not needed lmao. IDK why I opted to use it, but as others described you can just do single multiset and queue.

I think I did what you are describing. Basically, use a set to maintain the prefix of the sequence that is sorted, and a queue for the rest. For type 1 queries, you either add an element into the set if the queue is empty and the element is greater or equal to the highest value of the set, or you add it to the queue. For type 2 queries, you either remove the smallest element from the set or if the set is empty, just remove the front element of the queue. Lastly, for type 3 queries, you simply insert all the elements in the queue into the set. Make sure to use a multiset

Consider a subsequence l,r

if l and r are a good pair we can solve pair l,r, then the seq l+1,r-1.

And, we can solve l,l0 (in (l0-l)/2 steps), then l0+1,r

We need to combine all these combinations, with stars'n'bars formular.

I agree with you.It costs me a huge amount of time coding the similar problem : ARC070C qwq...

F: dp[L][R]: answer to the problem when you start with students numbered L, L+1, ..., R-1. (R-L must be even). dp[1][2N+1] is the answer.

For transition, iterate over all possible way of pairing student L. Let that student be M. We can't have any student between L and M paired with a student outside of the range [l, M]. Therefore, we can independently count those two separate range, and merge.

G: For fixed, k, we can solve it in O(k) with PIE. If we require z (0<=z<=k) groups to be empty, there are k choose z ways to choose such groups. Looking at a specific remainder R modulo M, there are either floor(N/M) or floor(N/M)+1 numbers with remainder R mod M. Each of those numbers contribute to the answer the exact same way. Do little bit of combinatorics to count the exact contribution.

curr = all; takes O(n^2) time.

Consider not using the set all. It is enough to have the curr set and the vector. On operation 3 push all elements from the vector into the set.

Op 3 is O(N), and is called up to N times, so O(N^2)

This is because upper_bound does not take advantage of structure of sets, as far as I know, upper_bound is implemented in a way such that it acts like binary search in an array but in sets elements are arranged differently so binary search doesn't works here and the function need to go for every element in order to return the desired result, giving worst case complexity of O(N). While set.upper_bound is implemented in a different way, so it works faster in O(logN).

Same is true for lower_bound and set.lower_bound too. :)

There can't be more than Q elements total to be inserted into the heap during the whole lifetime of the program. The amortized time complexity is $$$O(Q\ log\ Q)$$$.

CharlesWuQiushi Your Solution would give wrong answer for testCase mentioned below

3 3

1 4

2 3

5 6

Output: 3