GFSSOC '15 Fall J4 - Marathon - Olympiads Online Judge

GFSSOC '15 Fall J4 - Marathon

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 128M

Authors:

Problem type

It was a peaceful day in the life of a student, when suddenly Timothy Li messages you about some strange anime called Date a Live. There are $N$ $N$ episodes in the series, and each episode $i$ $i$ has a rating $k_i$ $k_{i}$ from 1 to 10. Being super bored, you decide to give it a try. Unfortunately, you cannot live without food through the entire afternoon and the anime streamer you are using does not have a pause button for some reason. Thus, to make an intelligent decision on when to go make food, you have $Q$ $Q$ queries in the form $a$ $a$ $b$ $b$ . For each of these queries, you will simulate skipping episodes $a$ $a$ to $b$ $b$ (inclusive), and output the sum of the ratings of the episodes you do not skip.

Input Specification

The first line of input contains 2 integers, space separated — $N, Q$ $N, Q$ .

The next line contains $N$ $N$ integers, space separated. The $i^{th}$ $i^{t h}$ of these integers represents the rating of the $i^{th}$ $i^{t h}$ episode.

The next $Q$ $Q$ lines contain integers $a_i$ $a_{i}$ and $b_i$ $b_{i}$ , the episodes that are skipped.

Output Specification

For each query, output one integer, the sum specified in the problem statement.

Constraints

$1 \le N, Q \le 500\,000$ $1 \leq N, Q \leq 500 000$

$1 \le k_i \le 10$ $1 \leq k_{i} \leq 10$

$1 \le a \le b \le N$ $1 \leq a \leq b \leq N$

Sample Input

Copy

10 3
5 6 7 8 3 4 5 6 1 2
1 3
2 4
1 10

Sample Output

Copy

29
26
0

Explanation of Output for Sample Input

For the first query, the first three episodes will be skipped, so the total rating is $8+3+4+5+6+1+2 = 29$ $8 + 3 + 4 + 5 + 6 + 1 + 2 = 29$ .

Comments

-13

Tristan_Louis commented on Feb. 22, 2023, 7:19 p.m.

this is like the easiest 7 pointer LOL

This comment is hidden due to too much negative feedback. Show it anyway.

12

EricHan commented on July 19, 2022, 12:47 a.m.

I have noticed a great correlation between the users of DMOJ and anime

-4

John commented on March 21, 2022, 6:47 p.m.

Ew, this isn't One Piece

1

trant8381 commented on Dec. 3, 2021, 9:59 p.m.

Date A Live! My favorite ever anime...

7

awaykened commented on April 2, 2015, 9:07 p.m. ← edit 2 →

For python/all users, it may/may not be advantageous to use fast input :)

-1

PerfectlyInternal commented on Nov. 11, 2020, 7:54 p.m.

This is pretty much the only optimization you need here if you use python, not much else is needed as long as you can get the correct answer.

0

bobhob314 commented on April 2, 2015, 10:00 p.m. ← edit 4 →

Thanks Weiwei!