| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12138 | too many treasures |
|
| 12125 | Tired janitor |
|
Description
Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas accidentally found an undiscovered tomb. He successfully sneaked in without triggering any traps. When he finally got into the treasure room, he found a note that warns tomb raiders about the trap in the treasure room. Osas arranged the note and concluded some rules:
- The treasure room has n treasure crates, each crate has its value. The values are sorted in descending order.
- There are several intervals [l,r] on the note.
- Tomb raiders must loot less than or equal to m treasure crates in the correct interval, where m is a number that Osas have to guess.
- If any tomb raider loot more than m treasure crates or loot any crate that not in the interval, the trap would trigger and kill that tomb raider! Osas doesn't want to die here.
Osas wants these treasures, but he doesn't want to die. Osas wants to know if he pick one interval and guess a number as "m", what is the maximum value he could loot? Osas asks you for help!
Osas will give you the value of every treasure crate and the number he would like to guess, you need to write a program to help him.
Input
The input contains exactly one testcase.
The first line contains two integers n, q. q indicates the amount of queries of (l,r,m).
The next line is the sequence of values of n treasure crates, each seperated by a space.
The next q lines, each line contains exactly three integers l, r, m.
1<=m<=n<=106, 1<=q<=106, 1<=l<=r<=n, m<=r-l+1, the value of every treasure crate won't larger than 105 or smaller than -105. All of the values are integers. Notice that the value could be negative, and Osas can choose nothing.
Note that the sequence index starts from 1. For example: for a sequence "a": "3 4 5 6 7", a[4]=6, a[1]=3.
Output
For each query, output the maximum value Osas could get. Each query holds exactly one line.
Remember to print a '\n' at the end of the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There were n rows of seats in the classroom. Each row of seats littered with ai unit of trash.
For example: first row contained a1 unit of trash
The janitor wanted to know how many units of trash were littered among row l to row r?
For example: If janitor ask you about row l = 3 to row r = 6. You should answer a3 + a4 + a5 + a6 unit of trash.
There will be q queries, help janitor find out the answer so janitor can clean up the class room.
Note that because janitor is furious about picking up trash, each number will be follow by a symbol " (/`A`)/ ~I__I " without quotation mark and then there is a blank to separate from the next number.
Note that if you use a loop to get the sum of al ~ ar at each query you will get an Time limit exceed.
You can use prefix sum to solve this problem
Input
input contains several lines.
First line contains two integer n(1 <= n <= 106), q(1 <= q <= 105) -- the number of rows and the number of queries.
Second line contains n integer a1 ~ an (0 <= ai <= 109), and each interger followed by a symbol " (/`A`)/ ~I__I " and then there is a blank to separate from the next number.
The following q lines each lines contains two integers l, r ( 1 <= l <= r <= n )
Output
output contain q lines, to each query output the sum of al ~ ar. remember to print \n at the end of each line.