레이팅 미적용\(N\) (\(1\le N\le 2\cdot 10^5\))개의 양동이가 쌓여 있는데, 위에서 \(i\)번째 양동이의 용량은 \(a_i\)갤런이다 (\(1\le a_i\le 10^9\)). 맨 위 양동이 위에 있는 수도꼭지는 초당 1갤런의 우유를 첫 번째 양동이에 보낸다. 양동이 \(N\) 아래에는 웅덩이도 있다.
어떤 양동이가 \(t\)초 후에 용량에 도달하면, \(t+1\)번째 초가 시작될 때 뒤집혀서 그 내용물을 마지막 양동이가 아니면 바로 아래 양동이에, 마지막 양동이이면 웅덩이에 쏟는다 (\(t+1\)번째 초가 끝날 때 다시 원래대로 돌아와 채워지기 시작한다). 양동이는 뒤집혀 있는 동안 우유를 받을 수 없다. 이 1초 동안 위 양동이에서 도착하는 우유는 모두 사라진다. 또한 아래 양동이의 용량을 초과하는 양의 우유도 모두 사라진다.
각각 세 정수 \(i\), \(v\), \(t\)로 주어지는 \(Q\) (\(1\le Q\le 3\cdot 10^5\))개의 쿼리를 처리하시오.
- 먼저 \(a_i=v\)로 설정한다 (\(1\le i\le N, 1\le v \le 10^9\)).
- 그런 다음 다음 질문에 답한다: 시각 \(0\)에 모든 양동이와 웅덩이가 비어 있다고 가정하자. \(t\)초 후 웅덩이에 있는 우유의 갤런 수를 구하시오 (\(1\le t\le 10^{18}\)).
\(a_i=v\) 갱신은 이후 쿼리에도 계속 유지된다.
문제 제공: Akshaj Arora
채점 방식
- 입력 4-5: \(N \le 10, Q\le 100\), 그리고 모든 \(t\le 10^4\)
- 입력 6-11: \(N\le 10^3, Q\le 10^4\)
- 입력 12-23: 추가 제약 조건이 없다.
문제 제공: Akshaj Arora
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(a_1\dots a_N\)이 주어진다.
다음 줄에 \(Q\)가 주어진다.
그다음 \(Q\)개의 줄에 세 정수 \(i\), \(v\), \(t\)가 주어진다. 이는 \(a_i=v\)로 설정한 뒤 \(t\)에 대한 질문에 답해야 한다는 의미이다.
각 질문에 대한 답을 한 줄에 하나씩 출력한다.
3
1 1 1
30
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 100
0
0
1
1
2
2
3
3
4
0
0
0
0
1
1
1
2
2
2
0
0
0
0
1
1
1
2
2
2When \(a=[1, 1, 1]\),
- Bucket \(1\) flips at times \(2,4,6,\dots\)
- Bucket \(2\) flips at times \(3,5,7,\dots\)
- Bucket \(3\) flips at times \(4,6,8,\dots\)
When \(a=[2, 1, 1]\),
- Bucket \(1\) flips at times \(3,6,9,\dots\)
- Bucket \(2\) flips at times \(4,7,10,\dots\)
- Bucket \(3\) flips at times \(5,8,11,\dots\)
When \(a=[2, 2, 1]\),
- Bucket \(1\) flips at times \(3,6,9,\dots\)
- Bucket \(2\) flips at times \(4,7,10,\dots\)
- Bucket \(3\) flips at times \(5,8,11,\dots\)
2
1 2
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 100
0
0
0
2
2
2
2
4
43
1 1 1
1
1 1 1000000000000000000499999999999999999riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Silver