Splitting Haybales | Code Joint

Farmer John wants to fairly split haybales between his two favorite cows Bessie and Elsie. He has $N$ ( $1 \leq N \leq 2 \cdot 1 0^{5}$ ) haybales sorted in non-increasing order, where the $i$ -th haybale has $a_{i}$ units of hay ( $2 \cdot 1 0^{5} \geq a_{1} \geq a_{2} \geq \dots \geq a_{N} \geq 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 \leq Q \leq 2 \cdot 1 0^{5}$ ) queries, each with three integers $l, r, x$ ( $1 \leq l \leq r \leq N$ , $∣ x ∣ \leq 1 0^{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.

For 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.

In 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.

SCORING:

Input 3: $Q \leq 100$
Inputs 4-6: At most $100$ distinct $a_{i}$
Inputs 7-22: No additional constraints.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

First line contains $N$ .

Second line contains $a_{1} \dots a_{N}$ .

Third line contains $Q$ .

Next $Q$ lines contain $l, r, x$ .

Output Format

Output $Q$ lines, containing the answer for each query.

Sample Input 1

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 2

Sample Output 1

1 2 3 -2 -1 0 1 2 -1 0 -1 0 1 0 1

Sample Input 2

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 2

Sample Output 2

16 12 7 4 1 2 1

Submit

Language