| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 12 | 4 | 4 | 33.333% |
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.
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 2
1 2 3 -2 -1 0 1 2 -1 0 -1 0 1 0 1
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.
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
16 12 7 4 1 2 1
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.