USACO 2023 February Contest, Platinum
Problem 1. Hungry Cow
Contest has ended.
Log in to allow submissions in analysis mode
**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 10^{14}$, $0\leq b_i \leq 10^9$).
Process $U$ ($1\le U\le 10^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 $10^9+7$.
INPUT FORMAT (input arrives from the terminal / stdin):
$U$, followed by $U$ lines containing the updates.OUTPUT FORMAT (print output to the terminal / stdout):
The sum after each update modulo $10^9+7$.SAMPLE INPUT:
3 4 3 1 5 1 2
SAMPLE OUTPUT:
15 36 18
Answers after each update:
4+5+6=15 1+2+3+4+5+6+7+8=36 1+2+4+5+6=18
SAMPLE INPUT:
9 1 89 30 7 101 26 1 24 5 1 60 4 5 10 101 0 1 200
SAMPLE OUTPUT:
4005 4656 7607 3482 3507 3753 4058 1107 24531
SCORING:
- Input 3: $U\le 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