CCO '10 P3 - Wowow

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.4s
Java 2.0s
Memory limit: 256M

Problem type
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!

Input Specification

The input will consist of an integer NN (1 \le N \le 1\,000\,000)(1 \le N \le 1\,000\,000), followed by NN lines. Each of these NN lines will correspond to one of the following three formats:

  • N X R, where NN is the character N to indicate a new friend has been added, XX is a number (1 \le X \le 1\,000\,000)(1 \le X \le 1\,000\,000) identifying this new friend, and RR (1 \le R \le 10^8)(1 \le R \le 10^8) is the rating of this new friend.
  • M X R, where MM is the character M to indicate a modification of an existing friend, XX is a number (1 \le X \le 1\,000\,000)(1 \le X \le 1\,000\,000) identifying one of your friends, and RR is the new rating assigned to this existing friend.
  • Q K, where QQ is the character Q to represent a query, KK is a number (1 \le K \le 1\,000\,000)(1 \le K \le 1\,000\,000), and KK 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 Specification

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

Sample Input

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

Sample Output



  • 5
    Riolku  commented on Nov. 22, 2018, 7:59 p.m.

    Is it possible to pass this with policy based data structures? Even with fast input I can't seem to get it under the time limit.

    • 5
      Kirito  commented on Nov. 22, 2018, 8:13 p.m.

      Yes, although I just barely managed to fit it under the time limit.

      • 5
        Riolku  commented on Dec. 16, 2018, 2:02 p.m.

        I managed to pass rather easily by changing an unordered_map to a simple array. Seems this one is on me.

  • 2
    sunnylancoder  commented on April 6, 2017, 10:38 p.m. edited

    Now it says:

    'No judge is availible for this problem'

    EDIT: NVM - working again

  • 4
    sunnylancoder  commented on April 2, 2017, 10:33 a.m.

    I'm not sure why my solution is TLEing - shouldn't n log n pass?

    • 5
      Kirito  commented on April 2, 2017, 4:06 p.m.

      You might need to constant optimise a little, since the time limit is a bit strict (even for C++).