2010 Canadian Computing Competition, Stage 2

Day 1, Problem 3: Wowow

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!

Input

The input will consist of an integer N (1 ≤ N ≤ 10⁶), followed by N lines. Each of these N lines will correspond to one of the following three formats:

• N X R, where N is the character 'N' to indicate a new friend has been added, X is a number (1 ≤ X ≤ 10⁶) identifying this new friend, and R (1 ≤ R ≤ 10⁸) is the rating of this new friend.
• M X R, where M is the character 'M' to indicate a modification of an existing friend, X is a number (1 ≤ X ≤ 10⁶) identifying one of your friends, and R is the new rating assigned to this existing friend.
• Q K, where Q is the character 'Q' to represent a query, K is a number (1 ≤ K ≤ 10⁶), and K 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.

Output

For each line of input of the format Q K, you will output a line containing the identifier of the Kth highest rated person in the database at that point. Note that when K = 1, that is the top rated person, and K = 2 is the second best rated person, and so on.

Sample Input

7
N 10 1000
N 3 1014
Q 1
M 10 2000
Q 1
N 65 1950
Q 2

Sample Output

3
10
65

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 3.00s
Memory Limit: 256M
Added: May 19, 2010

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

Comments (Search)

jungernaut165 on Apr 24, 2015 - 12:09:32 am UTC Hints?

• (0/0)

Hi all, I tried using a binary indexed tree approach.  For the fenwick tree, I create a list (using python) that is of size 10^8.  I get RE on my solution, which works for the sample.  Am I using the correct approach here?  Any suggestions of how to solve this problem?  Thank you in advance.

Hi all, I tried using a binary indexed tree approach. For the fenwick tree, I create a list (using python) that is of size 10^8. I get RE on my solution, which works for the sample. Am I using the correct approach here? Any suggestions of how to solve this problem? Thank you in advance.

jeffreyxiao on Apr 24, 2015 - 2:18:18 am UTC Re: Hints?

• (0/0)

You exceeded the memory limit.

You exceeded the memory limit.

jungernaut165 on Apr 24, 2015 - 5:23:24 am UTC Re: Hints?

• (0/0)

Hi Jeff, thanks for input.  Is my approach to use a BIT correct?  Or am headed in the wrong direction for this problem?  If it is correct to use BIT, then given that R can potentially be as large as 10^8, how do I not go about creating a fenwick tree without using that array size? 

Hi Jeff, thanks for input. Is my approach to use a BIT correct? Or am headed in the wrong direction for this problem? If it is correct to use BIT, then given that R can potentially be as large as 10^8, how do I not go about creating a fenwick tree without using that array size?

awaykened on Apr 24, 2015 - 5:01:23 pm UTC Re: Hints?

• (1/1)

You can use compression! :D (maps and stuff)

You can use compression! :D (maps and stuff)

jungernaut165 on Apr 25, 2015 - 1:00:43 am UTC Re: Hints?

• (0/0)

Hi Awaykened, Thanks for your input.  I'm fairly new.  Can you elaborate a little further of what you mean by compression, maps?  Thank you!

Hi Awaykened, Thanks for your input. I'm fairly new. Can you elaborate a little further of what you mean by compression, maps? Thank you!

fifiman on Apr 25, 2015 - 2:14:36 am UTC Re: Hints?

• (3/0)

You dont have to consider all the 10^8 possible ratings, just the ones that your friends will be using

You dont have to consider all the 10^8 possible ratings, just the ones that your friends will be using

awaykened on Apr 25, 2015 - 11:44:28 pm UTC Re: Hints?

• (0/1)

like fifiman said, if you have friends with IDs 1,6,8,10 you don't need to keep an array of 1 to 10, you only need an array of 1-4, and a map that looks something like {1:0,6:2,8:3,10:4}. That way when you need the person with ID 6, you look at your map and redirect to index 4 in your array. (This is not necessarily how you want to use maps in this question)

like fifiman said, if you have friends with IDs 1,6,8,10 you don't need to keep an array of 1 to 10, you only need an array of 1-4, and a map that looks something like {1:0,6:2,8:3,10:4}. That way when you need the person with ID 6, you look at your map and redirect to index 4 in your array. (This is not necessarily how you want to use maps in this question)

jungernaut165 on Apr 26, 2015 - 4:43:30 am UTC Re: Hints?

• (0/0)

Thank you much! So I am assuming you didn't use a binary indexed tree for this problem?

Thank you much! So I am assuming you didn't use a binary indexed tree for this problem?

awaykened on Apr 26, 2015 - 1:43:51 pm UTC Re: Hints?

• (1/1)

I passed with BIT + compression :biggrin:

I passed with BIT + compression

jungernaut165 on Apr 26, 2015 - 7:29:17 pm UTC Re: Hints?

• (0/0)

Ohh wow cool! Congrats!  Excuse my elementary understanding, but with a BIT you update at every incremented i & -i position.  If you used a hashtable, you might  not have keys when you compute the incremented i & -i positions.  How did you get around this?

Ohh wow cool! Congrats! Excuse my elementary understanding, but with a BIT you update at every incremented i & -i position. If you used a hashtable, you might not have keys when you compute the incremented i & -i positions. How did you get around this?

jargon on Apr 26, 2015 - 7:47:13 pm UTC Re: Hints?

• (1/0)

I think you're misunderstanding the point of the hashtable. Reread the above comments.

In any case, I wonder whether this is getting to be too much discussion about the answer... people looking for clarifications in the comments don't necessarily want to be given the solution.

I think you're misunderstanding the point of the hashtable. Reread the above comments.

In any case, I wonder whether this is getting to be too much discussion about the answer... people looking for clarifications in the comments don't necessarily want to be given the solution.

jungernaut165 on Apr 26, 2015 - 9:21:51 pm UTC Re: Hints?

• (0/0)

Hi there, I understand the point for a hashtable.  I just don't know how to apply a BIT to a hashtable.

Hi there, I understand the point for a hashtable. I just don't know how to apply a BIT to a hashtable.

bobhob314 on May 18, 2015 - 3:46:07 pm UTC Re: Hints?

• (0/0)

Python hashtable: Use integers as the keys. For each i & -i update, first check if the idx is in your dict; then update if it is.

Python hashtable: Use integers as the keys. For each i & -i update, first check if the idx is in your dict; then update if it is.

For last two cases, I'm pretty sure my answers are correct. I checked with official data.

endl appears to be causing the problem in your code. I think this is a judge/compiler issue. Use '\n' or printf for now.

If you have trouble solving this problem in Pascal due to the large amount of input data, tell me.