Hungry Cow | Code Joint

**Note: The time limit for this problem is 6s, three times the default. The memory limit for this problem is 512MB, twice the default.**

Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day $d_{i}$ , Farmer John sends a delivery of $b_{i}$ haybales ( $1 \leq d_{i} \leq 1 0^{14}$ , $0 \leq b_{i} \leq 1 0^{9}$ ).

Process $U$ ( $1 \leq U \leq 1 0^{5}$ ) updates as follows: Given a pair $(d, b)$ , update the number of haybales arriving on day $d$ to $b$ . After each update, output the sum of all days on which Bessie eats haybales modulo $1 0^{9} + 7$ .

Answers after each update:

4+5+6=15
1+2+3+4+5+6+7+8=36
1+2+4+5+6=18

SCORING:

Input 3: $U \leq 5000$
Inputs 4-10: Updates only increase the number of haybales arriving on day $d$ .
Inputs 11-22: No additional constraints.

Problem credits: Brandon Wang and Benjamin Qi

Source: USA Computing Olympiad.

Input Format

$U$ , followed by $U$ lines containing the updates.

Output Format

The sum after each update modulo $1 0^{9} + 7$ .

Sample Input 1

3 4 3 1 5 1 2

Sample Output 1

15 36 18

Sample Input 2

9 1 89 30 7 101 26 1 24 5 1 60 4 5 10 101 0 1 200

Sample Output 2

4005 4656 7607 3482 3507 3753 4058 1107 24531

Submit

Language