1B - Bear and Leaderboard

★★★★★

4.4

40 votes

Medium

Details

Submissions

Discussion

Editorial

Problem

Limak is a brown bear, experienced in organizing programming contests. Today, his only responsibility is to watch the leaderboard and make sure that everything is displayed correctly.

There are n participants, numbered 1 through n. Initially, every participant has 0 points. During the contest participants will gain more points and thus the leaderboard may change.

You are given q queries (events). The i-th query contains two integers $a_i$ and $b_i$ . It denotes that a participant $a_i$ gets $b_i$ points (his/her number of points is increased by $b_i$ ).

For each participant, his or her place is equal to the number of participants with more points, increased by 1. You may refer to the sample explanation for an example.

Let's define hash of participant as the product of his/her place and the number of points. After each query, Limak is going to find the sum of hashes of participants. Can you help him? After each query, print one line with the sum of hashes of participants.

Input format

The first line of the input contains two integers n and q — the number of participants and the number of queries, respectively.

The next q lines describe queries. The i-th of them contains two integers $a_i$ and $b_i$ — the participant index and the number of gained points in the i-th query.

Output format

After each query, output a single line containing the sum of hashes of participants.

Constraints

$1 \le n, q \le 500\,000$
$1 \le a_i \le n$
$1 \le b_i \le 10^6$

Subtasks

Extra constraints	Points	Which tests
$n, q \le 2000$	25	1-10
$b_i \le 5$	25	11-20
each participant will have at most $10^6$ points	25	21-30
no extra constraints	25	31-40

Sample Input

Sample Output

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

In the sample test, there are $n = 4$ participants. Initially, all of them have 0 points, so they all have the 1-st place ex aequo.

After the first query, participant 3 has $100$ points and is winning, with hash equal to $1 \cdot 100 = 100$ . The sum of hashes is $100 + 0 + 0 + 0 = 100$ .
After the second query, participant 2 has the second place with $60$ points and hash $2 \cdot 60 = 120$ , in total $100 + 120 + 0 + 0 = 220$ .
After the third query, the leaderboard looks like follows: $(100, 80, 60, 0)$ . The sum of hashes is $100 \cdot 1 + 80 \cdot 2 + 60 \cdot 3 + 0 \cdot 4 = 100+160+180 = 440$ .
In the fourth query participant 2 gets $20$ points and the leaderboard is $(100, 80, 80, 0)$ then, with the sum $100 \cdot 1 + 80 \cdot 2 + 80 \cdot 2 + 0 \cdot 4 = 420$ .
After the fifth query, the answer is $100 \cdot 1 + 100 \cdot 1 + 80 \cdot 3 + 0 = 440$ .
After the last query, $100 \cdot 1 + 100 \cdot 1 + 80 \cdot 3 + 17 \cdot 4 = 508$ .

Contributers:

Errichto Dębowski

Błażej Magnowski