GFSSOC '15 Fall J5 - Nightmare-a-thon - DMOJ: Modern Online Judge

GFSSOC '15 Fall J5 - Nightmare-a-thon

Points: 10 (partial)

Time limit: 2.5s

Memory limit: 128M

Authors:

Problem types

You were 9 episodes into Date a Live when you noticed that something was wrong. Who is this Kurumi character? That is when you realize you were watching Date a Live 2 the entire time. Now you need to go through the difficult ordeal of marathoning Date a Live through the night! Unfortunately, you cannot live without food through the entire night, and the anime streamer you are using still does not have a pause button. This means out of the $N$ $N$ total episodes, you need to skip some continuous episodes to go downstairs and eat something. Luckily, you have the overall ratings for the episodes, out of 10! The $i^{th}$ $i^{t h}$ episode has a user rating of $k_i$ $k_{i}$ . In order to determine the best time to go make food, you have $Q$ $Q$ queries — each query asking the highest episode rating you can watch if you skip episodes $a$ $a$ to $b$ $b$ (inclusive) and how many episodes with this rating there are. It is guaranteed for any query, there will be at least one episode that you do not skip.

Input Specification

Line 1: two integers space separated, $N$ $N$ and $Q$ $Q$ .

Line 2: $N$ $N$ spaced integers, holding the rating for each episode, from $1$ $1$ to $10$ $10$ .

The next $Q$ $Q$ lines will contain integers $a$ $a$ and $b$ $b$ $(1 \le a \le b \le N)$ $(1 \leq a \leq b \leq N)$ .

Output Specification

For each query, output two integers space separated. The first integer should be the highest rated episode that isn't skipped, and the second integer should be the number of episodes with this rating.

Constraints

Subtask 1 [30%]

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

Subtask 2 [70%]

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

Sample Input

Copy

7 2
5 4 5 2 3 1 5
2 4
1 6

Sample Output

Copy

5 2
5 1

Explanation of Output for Sample Input

For the first query, episodes 2 to 4 will be skipped, leaving you with episode ratings: 5 x x x 3 1 5. The highest rated episode is 5, and both episodes 1 and 7 have this rating.

Comments

53

4fecta commented on Aug. 11, 2019, 9:55 p.m.

Given that the maximum rating of an episode is 3628800 (10!), those episodes must have been trash.

4

Dormi commented on Aug. 29, 2017, 10:31 p.m.

UMM in, "The first integer should be the highest rated episode that isn't skipped, and the second integer should be the number of episodes with this rating." and "The highest rated episode is 5, and both episodes 1 and 7 have this rating." You say "the highest rated episode" meaning you're asking for the episode which has the highest rating and not the highest episode rating.

23

omaewamoushindeiru commented on May 5, 2015, 2:15 a.m.

One day..my keyboard will fly out the window.

29

kobortor commented on May 5, 2015, 12:50 p.m.

And you along with it.

25

omaewamoushindeiru commented on May 5, 2015, 1:38 p.m.

do you wanna die

16

kobortor commented on May 5, 2015, 2:13 p.m.

Do you want to solve sketchly park?

11

Pleedoh commented on Aug. 1, 2017, 2:43 a.m.

that's a fun one