News headline generator (Ranking via heaps)

• Problem definition
• Suggested approach
• Input/output formats
• Requirements
• Datasets

Problem definition

In this assignment, you need to implement a news management system that can store a lot of news items, and each item is associated with a score of popularity. In particular, your system should support the following operations:

• Insert: Insert a news item, and all the existing news items have to depreciate by deducting a given number from their original scores.
• Update: For a given set of news ID, we can increase their scores by a given number.
• Query: output the highest-score news ID, and its score.

Suggested approach

Vector-based heaps.

Input/output formats

• Input format
  • The first line contains two integer, $n$ (the number of operations) and $k$ (the number to be deducted for the existing news items when a new item is added).
  • For each of the following $n$ lines, the first integer is $m_i$ which indicates the mode of operation to be executed.
    • If $m_i=1$ (insert), it will be followed by $d_i$ (news ID) and $s_i$ (news score), with $0 \leq d_i \leq 10^6$, and $0 \leq s_i \leq 10^6$.
    • If $m_i=2$ (update), it will be followed by $v_i$ (the number to be added to scores of the following news ID), $c_i$ (number of news items to be updated), and list of $c_i$ news IDs for update. Note that $0 \leq v_i \leq 10^6$ and $1 \leq c_i \leq 5$.
    • If $m_i=3$ (query), output the news ID with the highest score. (If there is a tie, output the news ID that was inserted most recently.)
  Here is an example input file: 20 80025 1 15 356051 1 2 392134 1 0 407336 1 7 517303 1 3 631251 2 337391 5 15 15 0 0 0 3 2 471959 2 3 2 2 15587 5 15 2 7 0 15 1 17 139590 2 858380 3 3 17 7 3 1 19 309860 2 102611 4 7 7 17 19 3 1 14 704404 1 10 213329 2 558447 1 0 1 18 609195 3
• Output format
  • For each query, output a line, as shown in the example output file.
  Here is an example output file: id: 0, value: 1259459 id: 3, value: 1881565 id: 3, value: 1801540 id: 3, value: 1561465

Requirements

• Limits:
  • Max time: 2 sec (for n=$10^6$).
  • Max memory: 256 MB.
  • Max submissions: 20 times each week.
• Program usage: Your program should take standard input and generate standard output: myProgram < input.txt > output.txt

Datasets

1. Open test sets
   • open01.txt, open01_out.txt
   • open02.txt, open02_out.txt
   • open03.txt, open03_out.txt
   • open04.txt, open04_out.txt