GFSSOC '15 Fall J4 - Marathon

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

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 episodes in the series, and each episode i has a rating 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 queries in the form a b. For each of these queries, you will simulate skipping episodes a to 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.

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

The next Q lines contain integers a_i and b_i, the episodes that are skipped.

Output Specification

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


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

1 \le k_i \le 10

1 \le a \le b \le N

Sample Input

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

Sample Output


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.


  • 1
    trant8381  commented on Dec. 3, 2021, 4:59 p.m.

    Date A Live! My favorite ever anime...

  • 1
    Xue_Alex  commented on May 21, 2017, 8:11 p.m.

    I have a question regarding my submissions. I submitted the exact same code line for line 3 different times, and one on one of them, I got 5/10 AC (with the others being TLE), on one of them I got 6/10 AC (with the others being TLE), and on the last I got 7/10 AC (with the others being TLE). Does anyone know why this may be?

    • 2
      AWB  commented on July 16, 2017, 7:55 p.m.

      The different judges might operate at varying speeds.I think we're in the same boat: I implemented what the editorial called for, yet still, I got TLE on the last three :/

  • 7
    awaykened  commented on April 2, 2015, 5: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, 2: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, 6:00 p.m. edit 4

      Thanks Weiwei!