National Olympiad in Informatics, China, 2004

Day 1, Problem 1 - The Depressed Cashier

OIER Ltd. is a large specialization software company with tens of thousands of employees. Being one of its cashiers, one of my jobs is to work with each employee's salary. This is normally not a bad job, but what makes it depressing is that my boss can never make up his mind. He frequently adjusts his employee's wages. If he's in the mood, he might add a fixed amount to each employee's wage. Contrarily, if he's unhappy, he just might just deduct a fixed amount from each employee's wage. We really don't even know what else he does besides adjusting wages all day long.

The frequent adjustment of wages makes employees very resentful, especially when it's a deduction. Once an employee discovers that their wage has fallen below the minimum promised wage in their contract, they will immediately leave the company in anger, never to return. The lower bound of each employee's wage are uniformly regulated. Whenever an employee leaves the company, we need to delete their records from the computer. Similarly, whenever the company hires a new employee, we have to create a new record for them.

The boss often comes over to inquire about the status of wages. He never asks me about the wages of any specific employee. Instead he asks for the wage of the k-th highest paid employee. Whenever this happens, I can't help but perform a long and tedious sorting of the tens of thousands of employees in order to finally report the answer to him.

Alright. Now you've learned enough about my job. Just as you probably guessed, I would like you to please write a program that manages the wage information of the employees. How does that sound? Not too difficult, right?

Input Format

The first line contains two non-negative integers n and min, representing the number of commands and the minimum regulated wage in all the employees' contracts, respectively.

Each of the next n lines contains a single command that is one of the four following types:

In each of the Initialize, Add, and Subtract commands, k will be a non-negative integer. In Find commands, k will be a positive integer. Assume that initially, there are no employees in the company.

Output Format

There number of lines in the output is the number of Find commands plus 1. For each Find command, your program must output one line containing a single integer, the wage of the k-th highest paid employee a that time. If k is greater than the number of employees in the company at the time, then output -1.

The last line of output should contain a single integer - the total number of employees that has left the company.

Sample Input

9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2

Sample Output

10
20
-1
2

Constraints

• The number of Initialize commands will not exceed 100000.
• The total number of Add and Subtract commands will not exceed 100.
• The number of Find commands will not exceed 100000.
• For each wage adjustment, the amount adjusted will not exceed 1000.
• A new employee's wage starting wage will not exceed 100000.

Scoring

For each test case, your score out of 10 will be determined as follows:

• If there are an incorrect number of values in your output, then your score will be 0.
• Otherwise, your score will be calculated as follows:
  • If for all Find commands you output the correct answer, and for the last value you also output the correct answer, then you will score 10 points.
  • If you correctly determine the answer to all Find commands, but not the number of employees that left, then you will score 6 points.
  • If you only determine the number of employees that left, then you will score 4 points.
  • Otherwise, your score will be 0 points.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 19, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Apparently, the final line of output should not include employees who leave immediately (due to their initial wage being below the minimum).