레이팅 미적용농부 존은 가장 아끼는 두 소 베시와 엘시에게 건초 더미를 공평하게 나누어 주고 싶다. 그에게는 비오름차순으로 정렬된 \(N\)(\(1\le N\le 2\cdot 10^5\))개의 건초 더미가 있으며, \(i\)번째 건초 더미에는 \(a_i\) 단위의 건초가 들어 있다 (\(2\cdot 10^5\ge a_1\ge a_2 \ge \dots \ge a_N \ge 1\)).
농부 존은 연속한 범위의 건초 더미 \(a_l, \dots, a_r\)을 베시와 엘시에게 나누어 주는 것을 고려하고 있다. 그는 건초 더미를 \(l\)부터 \(r\)까지 순서대로 처리하기로 했으며, \(i\)번째 건초 더미를 처리할 때 현재 건초가 더 적은 소에게 그것을 준다 (같으면 베시에게 준다).
\(Q\)(\(1\le Q\le 2\cdot 10^5\))개의 쿼리가 주어지며, 각 쿼리는 세 정수 \(l,r,x\)(\(1\le l\le r\le N\), \(|x|\le 10^9\))로 이루어진다. 각 쿼리에 대해, 베시가 엘시보다 \(x\) 단위 더 많은 건초를 가진 상태에서 시작할 때, 건초 더미 \(l\)부터 \(r\)까지 처리한 후 베시가 엘시보다 몇 단위 더 많은 건초를 가지게 되는지 출력한다. 엘시가 베시보다 더 많이 가지게 되면 이 값은 음수임에 유의하자.
문제 제공: Benjamin Qi
배점
- 입력 3: \(Q\le 100\)
- 입력 4-6: 서로 다른 \(a_i\)가 최대 \(100\)개
- 입력 7-22: 추가 제약 없음.
문제 제공: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(a_1\dots a_N\)이 주어진다.
셋째 줄에 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 \(l, r, x\)가 주어진다.
각 쿼리의 답을 담은 \(Q\)개의 줄을 출력한다.
2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 21
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1For the 1st query, Elsie starts with \(2\) more hay than Bessie. Then, after
processing haybale \(1\), Bessie will receive \(3\) hay, and Bessie will have \(1\)
more hay than Elsie.
For the 3rd query, Elsie and Bessie start with the same number of hay. After
processing haybale \(1\), Bessie will receive \(3\) hay, and Bessie will have \(3\)
more hay than Elsie.
For the 9th query, Bessie starts with \(1\) more hay than Elsie, then after
processing the 1st haybale, has \(2\) less hay than Elsie, and after processing
the 2nd haybale, has \(1\) less hay than Elsie.
5
4 4 3 1 1
7
1 1 20
1 2 20
1 5 20
1 1 0
1 5 0
1 4 0
3 5 216
12
7
4
1
2
1In the 5th query, there are \(5\) haybales to process. Bessie receives \(4\) hay, then Elsie
receives \(4\) hay, then Bessie receives \(3\) hay, then Elsie receives \(1\) hay,
then Elsie receives \(1\) hay.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Platinum