레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 3배인 6초이다. 메모리 제한은 기본의 2배인 512MB이다.*
베시는 배고픈 소이다. 매일 저녁 식사 때, 헛간에 건초 더미가 있으면 베시는 건초 더미 하나를 먹는다. 농부 존은 베시가 굶는 것을 원치 않으므로, 어떤 날에는 건초 더미 배송을 보내며, 배송은 아침(저녁 식사 전)에 도착한다. 구체적으로, \(d_i\)일에 농부 존은 \(b_i\)개의 건초 더미 배송을 보낸다 (\(1\leq d_i \leq 10^{14}\), \(0\leq b_i \leq 10^9\)).
다음과 같은 \(U\) (\(1\le U\le 10^5\))개의 갱신을 처리하라: 쌍 \((d, b)\)가 주어지면, \(d\)일에 도착하는 건초 더미의 개수를 \(b\)로 갱신한다. 각 갱신 후, 베시가 건초 더미를 먹는 모든 날의 합을 \(10^9+7\)로 나눈 나머지를 출력한다.
출제자: Brandon Wang, Benjamin Qi
배점
- 입력 3: \(U\le 5000\)
- 입력 4-10: 갱신은 \(d\)일에 도착하는 건초 더미의 개수를 증가시키기만 한다.
- 입력 11-22: 추가 제약 조건이 없다.
출제자: Brandon Wang, Benjamin Qi
\(U\)가 주어지고, 이어서 \(U\)개의 줄에 갱신이 주어진다.
각 갱신 후의 합을 \(10^9+7\)로 나눈 나머지를 출력한다.
3
4 3
1 5
1 215
36
18Answers after each update:
4+5+6=15
1+2+3+4+5+6+7+8=36
1+2+4+5+6=18
9
1 89
30 7
101 26
1 24
5 1
60 4
5 10
101 0
1 2004005
4656
7607
3482
3507
3753
4058
1107
24531riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Platinum