I Hate Ready to Program P2 - Graphics Galore

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.5s
Memory limit: 128M

Problem type
Allowed languages
Assembly, Awk, Brain****, C, C++, Clang, Clang++, COBOL, Coffee, D, Fortran, Go, Haskell, Java, JS, Kotlin, Lisp, LOLCODE, Lua, Mono C#, Mono F#, NASM, NASM64, OCaml, Pascal, Perl, PHP, Processing, Racket, Ruby, Rust, Sed, TCL, Text, Turing

It's graphics time! For an assignment, you used separate methods to draw your N objects. However, it seems that Ready to Program cannot seemingly handle all your (totally) amazing drawings (without exploding and probably somehow cause the RtP equivalent of an IE on DMOJ)! You have given each of your objects a value, v_i, which represents their style point. You also created Q queries to determine how many style points you will receive if you commented out every object except those in the range of the query. Out of these queries, determine the maximum number of style points you can score!

DISCLAIMER: Python CANNOT PASS (and now is no longer a submittable language)


1 \leq L_i < R_i \leq N

Subtask 1 [20%]

1 \leq N,Q \leq 10^3

Subtask 2 [80%]

1 \leq N,Q \leq 10^6

-10^5 \leq v_i \leq 10^5

Input Specifications

The first line will contain two space-separated integers, N,Q.

The next line will contain N space-separated integers, v_1,v_2,v_3,...v_n, the style points of each object.

The next Q lines will contain two space-separated integers L_i,R_i, describing the range [L_i,R_i] of the indices, inclusive.

Output Specifications

The first Q lines of your output should contain a single integer on each line, the sum of all the style points from L_i to R_i.

The Q+1th line should contain an integer M, with 1 \leq M \leq Q, the query that has the highest style points. If there is a tie, output the query that appears first in the sample input.

Sample Input

3 2
5 6 -1
1 2
2 3

Sample Output


Sample Case Explanation

The first query contains the objects 5 and 6, which has a sum of 11. The second query contains the objects 6 and -1, which has a sum of 5. Since query 1 has a greater value than query 2, then the number on the last line is 1.


There are no comments at the moment.