Let us call an operation with \(t_i = 1\) an assignment and an operation with \(t_i = 2\) an addition.

Once an assignment is performed, all the operations so far is forgotten. Suppose that the \(k\)-th operation is the last assignment performed. We can assume that every operation before the \(k\)-th operation is performed, and every assignment later than \(k\)-th operation (suppose that there are \(n\) such operations) must be ignored. If \(n \gt K\), then the \(k\)-th operation cannot be the last assignment, so we suppose \(n \leq K\).

By the observation above, the problem is boiled down to a problem of maximizing the sum of values being added to \(x\) by ignoring between \(0\) and \(K-n\) (inclusive) of the additions later than the \(k\)-th operation. The optimal choice can be determined by inspecting the additions later than the \(k\)-th operation in the increasing order of \(y_i\) and deciding to ignore the operations where \(y_i < 0\) at most \(K - n\) times. However, we cannot sort \(y_i\) to decide the operations to ignore for every \(k\), because it will exceed the time limit.

Instead, let iterate \(k\) in the decreasing order and, instead of choosing the operations from scratch, reuse the previous result. Let \(S\) be the multiset of \(y_i\) in the ignored additions, and \(T\) be the multiset of the other additions, then the maximum is achieved if all of the following conditions are satisfied:

• \(|S| \leq K - n\)
• \(\displaystyle \max_{x \in S} x \leq \min_{x \in T} x\)
• \(x \in S \Rightarrow x \lt 0\)
• \(|S| \lt K - n \Rightarrow \min_{x \in T} x \geq 0\)

Also, every time we process new \(k\), there are the following two updates:

• Case 1: we gain one more addition to ignore. That is, \(n\) increases by \(1\).
• Case 2: we gain one more addition to be considered.

Case 1: when replacing \(n\) with \(n' = n + 1\),

• If \(|S| \lt K - n\), do nothing.
• If \(|S| = K - n\), then \(|S| \gt K - n'\), so remove the maximum value of \(S\) from \(S\) and add it to \(T\).

Then, the conditions above is still satisfied after \(n\) is replaced with \(n'\).

Case 2: when considering new addition such that \(y_i = y'\),

• If \(y' \geq 0\), then add \(y'\) to \(T\).
• If \(y' \lt 0\), add \(y'\) to \(S\). If this makes \(|S| \gt K - n\), remove the maximum value of \(S\) from \(S\) and add it to \(T\).

Then, the conditions above is still satisfied after \(y'\) is replaced.

All of these operations can be implemented with maximum/minimum heaps. By maintaining the sum of elements in \(T\), the maximum value can be computed fast enough. The numbers of elements of \(S\) and \(T\) change at most \(O(N)\) time in total, so the problem has been solved in a total of \(O(N \log N)\) time.

The implementation will be easier by considering an additional operation of \(t_0 = 1, y_0 = 0\).

Sample code (C++) :