Canadian Computing Competition: 2010 Stage 2, Day 1, Problem 3
In the World of World of Warcraft, there is a very competitive ladder system. Sometimes players will change their rating. Also, new players (including more and more of your friends!) are constantly joining the game.
You and your group of friends would like to maintain a simple database with your scores, and you, as the computer scientist of the group, have been charged with the responsibility of maintaining it. Don't let your friends down!
The input will consist of an integer , followed by lines. Each of these lines will correspond to one of the following three formats:
N X R, where is the character
Nto indicate a new friend has been added, is a number identifying this new friend, and is the rating of this new friend.
M X R, where is the character
Mto indicate a modification of an existing friend, is a number identifying one of your friends, and is the new rating assigned to this existing friend.
Q K, where is the character
Qto represent a query, is a number , and is at most the number of your friends that have a rating at this point.
You may assume there will be no identical ratings in the input.
For each line of input of the format
Q K, you will output a line containing the identifier of the highest rated person in the database at that point. Note that when , that is the top rated person, and is the second best rated person, and so on.
7 N 10 1000 N 3 1014 Q 1 M 10 2000 Q 1 N 65 1950 Q 2
3 10 65