![]() |
||||||||||
|
||||||||||
Queue SequenceTime Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2157 Accepted Submission(s): 593 Problem Description There's a queue obeying the first in first out rule. Each time you can either push a number into the queue (+i), or pop a number out from the queue (-i). After a series of operation, you get a sequence (e.g. +1 -1 +2 +4 -2 -4). We call this sequence a queue sequence. Now you are given a queue sequence and asked to perform several operations: 1. insert p First you should find the smallest positive number (e.g. i) that does not appear in the current queue sequence, then you are asked to insert the +i at position p (position starts from 0). For -i, insert it into the right most position that result in a valid queue sequence (i.e. when encountered with element -x, the front of the queue should be exactly x). For example, (+1 -1 +3 +4 -3 -4) would become (+1 +2 -1 +3 +4 -2 -3 -4) after operation 'insert 1'. 2. remove i Remove +i and -i from the sequence. For example, (+1 +2 -1 +3 +4 -2 -3 -4) would become (+1 +2 -1 +4 -2 -4) after operation 'remove 3'. 3. query i Output the sum of elements between +i and -i. For example, the result of query 1, query 2, query 4 in sequence (+1 +2 -1 +4 -2 -4) is 2, 3(obtained by -1 + 4), -2 correspond. Input There are less than 25 test cases. Each case begins with a number indicating the number of operations n (1 ≤ n ≤ 100000). The following n lines with be 'insert p', 'remove i' or 'query i'(0 ≤ p ≤ length (current sequence), 1 ≤ i, i is granted to be in the sequence). In each case, the sequence is empty initially. The input is terminated by EOF. Output Before each case, print a line "Case #d:" indicating the id of the test case. After each operation, output the sum of elements between +i and -i. Sample Input
Sample Output
Source | ||||||||||
|