| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12125 | Tired janitor |
|
| 12127 | too many words |
|
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.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas just got some writing homework to do.
His teacher gave him some texts, then asked him to write all of these texts once, and by hand.
However, Osas wants to cheat, so he ask you to write a program to repeat these texts exactly once so that he can just print them onto an A4 paper and turn in the homework easily.
(Although you know that finish the work by computer and printer, he will definitely get a ZERO, however, you still have to complete your task to get your AC.)
Input
The input contains a lot of texts. You don't know when will the text ends, but you know that there must be EOF at the end of the input.
And you know that the total amount of characters won't exceed 107.
Output
Print exactly the same as the input, even spaces and wraps('\n').