DMOPC '15 Contest 2 P5 - Sysadmin

View as PDF

Submit solution


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

Authors:
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,,N1, appear to have memory leaks. That is, program i's memory usage increases by Mi KB every second, each starting from a distinct Si 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 Qi seconds. There might be multiple, in which case he'd like to know the one with the smallest identifier.

Constraints

For all subtasks:

1Mi1000

1Si1000000

Subtask 1 [20%]

1N500

1Q500

Subtask 2 [80%]

1N100000

1Qi500000

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 Si, and Mi.
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

Copy
2 2
400 100
200 200
1
10

Sample Output

Copy
0
1

Explanation

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.


Comments


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

    We all get TLEs...


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

      i used scanf and printf and it passed for me.


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

      Agreed