SAC '21 P4 - Averaging Averages

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

To get into university, you are required to have a high average, so your advisor offers you a challenge:

If you can answer my Q queries, I will boost your average by 1\%.

Each query will consist of [L, R], meaning your advisor wants you to query the average of courses L, L + 1, \dots, R rounded down to the nearest integer.

Input Specification

The first line will contain N and Q, the number of courses you are currently taking and the number of queries.

The second line will contain N space-separated integers, A_i, your average in the i^\text{th} course.

The next Q lines will contain L and R, a query for the average of your courses in [L, R].

Note: Fast I/O might be required to fully solve this problem (e.g., BufferedReader for Java)

Output Specification

Output Q lines, the answer to each query rounded down to the nearest integer.


For all subtasks:

1 \leq N, Q \leq 1\,000\,000

1 \leq L \leq R \leq N

0 \leq A_i \leq 100

Subtask 1 [50%]

1 \leq N, Q \leq 1\,000

Subtask 2 [50%]

No additional constraints.

Sample Input

5 3
100 50 0 75 90
1 2
2 3
2 5

Sample Output



There are no comments at the moment.