Political Instability

View as PDF

Submit solution

Points: 17
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

After the end of the war, Collea was left in a state of political turmoil. Having been forced to install a democratic government, and with the rise of extremist attitudes throughout the country, the current Collean government is anxious about the coming national election. There are N political parties in Collea, which are conveniently numbered from 1 to N, and current polls show that if the election was to be held today, the ith political party would earn v_i votes. In order for a new government to form, some of the political parties must form a majority coalition where the sum of the votes of the parties in the coalition must be strictly greater than half of the total votes. In the D following days, some political parties had their expected number of votes changed. Specifically, on the ith day, the a_ith party's expected number of votes changed to b_i. Help Collea find the minimum number of parties required such that they form a majority coalition for each day.

Constraints

1 \leq N \leq 300\space 000
0 \leq D \leq 300\space 000
0 \leq b_i,v_i \leq 10^9
1 \leq a_i \leq N
It is guaranteed that the total number of votes will always be positive.

Subtask 1 [10%]

1 \leq N,D \leq 2000

Subtask 2 [90%]

No additional constraints

Input Specifications

The first line contains two integers, N and D.
The second line contains N integers, v_1,v_2\ldots,v_N
D lines follow, the ith of which contains the integers a_i and b_i

Output Specifications

On the first line, output one integer, the minimum possible number of parties in a majority coalition before the D days.
Output D more lines, the ith of which containing one integer, the minimum possible number of parties in a majority coalition after the ith day.

Sample Input

5 3
3 1 5 2 2
2 3
5 3
4 5

Sample Output

2
2
3
2

Comments


  • 1
    NT_AUTHORITY_SYSTEM  commented on Jan. 5, 2019, 1:49 a.m. edit 2

    Having been forced to install a democratic government, and with the rise of extremist attitudes rising throughout the country


    • 0
      Kirito  commented on Jan. 5, 2019, 11:34 a.m.

      Typos have been fixed.


  • 0
    SourSpinach  commented on Jan. 2, 2019, 8:21 a.m. edited

    I'd suggest adding a maximal case with many equal v values (e.g. all v values initially equal to 1, and then updated one-by-one to be equal to 2), as such cases can cause some solutions to change from O(N log(N)) to O(N^2) and time out (such as my first submission).