LKP '18 Contest 2 P5 - Political Instability

View as PDF

Submit solution

Points: 17
Time limit: 2.5s
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 \le N \le 300\,000
0 \le D \le 300\,000
0 \le b_i,v_i \le 10^9
1 \le a_i \le N
It is guaranteed that the total number of votes will always be positive.

Subtask 1 [10%]

1 \le N,D \le 2000

Subtask 2 [90%]

No additional constraints.

Input Specification

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

Output Specification

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


  • 0
    SourSpinach  commented on Jan. 2, 2019, 1:21 p.m. edit 2

    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 \mathcal{O}(N \log N) to \mathcal{O}(N^2) and time out (such as my first submission).