DMOPC '15 Contest 2 P5 - Sysadmin

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

Every day as the sun sets, quantum opens up his terminal and connects to the DMOJ site server. Like any sysadmin, quantum likes statistics about anything and everything. Today, he's interested in the memory usages of all the applications running on the server.

As he runs top, he notices that N programs, identified 0, \dots, N-1, appear to have memory leaks. That is, program i's memory usage increases by M_i KB every second, each starting from a distinct S_i KB. Finding this race of programs fun to watch, quantum would like to answer Q queries: for each query i, he'd like to know which program has the greatest memory usage after Q_i seconds. There might be multiple, in which case he'd like to know the one with the smallest identifier.


For all subtasks:

1 \le M_i \le 1\,000

1 \le S_i \le 1\,000\,000

Subtask 1 [20%]

1 \le N \le 500

1 \le Q \le 500

Subtask 2 [80%]

1 \le N \le 100\,000

1 \le Q_i \le 500\,000

Input Specification

The first line of input will contain the space-separated integers N and Q.
For the next N lines of input, line i will contain two integers S_i, and M_i.
Finally, the last Q lines will each contain a query.

Output Specification

For each query, the id of the program using the most memory at the given time.

Sample Input

2 2
400 100
200 200

Sample Output



After the 1 second, program 1 uses 500 KB of memory, while 2 uses only 400 KB. Following 10 seconds, program 2 is in the lead, with 2200 KB of memory used.


  • 0
    r3mark  commented on Dec. 15, 2015, 5:24 p.m.

    What happened to the judge?

    • 4
      Xyene  commented on Dec. 15, 2015, 6:12 p.m.

      I was updating the software on the Herculaneum judge as well as adding Swift support (seeing as Apple open-sourced it a few days ago). It's back online now, sorry for the delay.

  • 13
    Walt28  commented on Nov. 11, 2015, 3:03 p.m. edit 4

    We all get TLEs...

    • 2
      baal_hammon  commented on Nov. 22, 2015, 12:12 p.m.

      i used scanf and printf and it passed for me.

    • 5
      WallE256  commented on Nov. 11, 2015, 3:27 p.m.