
ZOJ Problem Set  1319
Our Black Box represents a primitive database. It can save an integer array and has a special i variable. At the initial moment Black Box is empty and i equals 0. This Black Box processes a sequence of commands (transactions). There are two types of transactions: ADD(x): put element x into Black Box;
N Transaction i Black Box contents after transaction Answer (elements are arranged by nondescending) 1 ADD(3) 0 3 2 GET 1 3 3 3 ADD(1) 1 1, 3 4 GET 2 1, 3 3 5 ADD(4) 2 4, 1, 3 6 ADD(2) 2 4, 1, 2, 3 7 ADD(8) 2 4, 1, 2, 3, 8 8 ADD(1000) 2 1000, 4, 1, 2, 3, 8 9 GET 3 1000, 4, 1, 2, 3, 8 1 10 GET 4 1000, 4, 1, 2, 3, 8 2 11 ADD(2) 4 1000, 4, 1, 2, 2, 3, 8 It is required to work out an efficient algorithm which treats a given sequence of transactions. The maximum number of ADD and GET transactions: 30000 of each type. Let us describe the sequence of transactions by two integer arrays:
2. u(1), u(2), ..., u(N): a sequence setting a number of elements which are being included into Black Box at the moment of first, second, ... and Ntransaction GET. For the Example we have u=(1, 2, 6, 6). The Black Box algorithm supposes that natural number sequence u(1), u(2), ..., u(N) is sorted in nondescending order, N <= M and for each p (1 <= p <= N) an inequality p <= u(p) <= M is valid. It follows from the fact that for the pelement of our u sequence we perform a GET transaction giving pminimum number from our A(1), A(2), ..., A(u(p)) sequence.
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks. The output format consists of N output blocks. There is a blank line between output blocks.
1 7 4
3 Source: Northeastern Europe 1996 