Splitting Haybales
다이아몬드 II의견: 0
Farmer John wants to fairly split haybales between his two favorite cows Bessie
and Elsie. He has \(N\) ( \(1\le N\le 2\cdot 10^5\)) haybales sorted in
non-increasing order, where the \(i\)-th haybale has \(a_i\) units of hay
(\(2\cdot 10^5\ge a_1\ge a_2 \ge \dots \ge a_N \ge 1\)).
Farmer John is considering splitting a contiguous range of haybales
\(a_l, \dots, a_r\) between Bessie and Elsie. He has decided to process the
haybales in order from \(l\) to \(r\), and when processing the \(i\)-th haybale he
will give it to the cow who currently has less hay (if it is a tie, he will give
it to Bessie).
You are given \(Q\) (\(1\le Q\le 2\cdot 10^5\)) queries, each with three integers
\(l,r,x\) (\(1\le l\le r\le N\), \(|x|\le 10^9\)). For each query, output how many
more units of hay Bessie will have than Elsie after processing haybales \(l\) to
\(r\), if Bessie starts with \(x\) more units than Elsie. Note that this value is
negative if Elsie ends up with more haybales than Bessie.
Problem credits: Benjamin Qi
SCORING
- Input 3: \(Q\le 100\)
- Inputs 4-6: At most \(100\) distinct \(a_i\)
- Inputs 7-22: No additional constraints.
Problem credits: Benjamin Qi
First line contains \(N\).
Second line contains \(a_1\dots a_N\).
Third line contains \(Q\).
Next \(Q\) lines contain \(l, r, x\).
Output \(Q\) lines, containing the answer for each query.
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
평가 및 의견
Splitting Haybales
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Splitting Haybales