oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

collectmushrooms2 Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

collectmushrooms2.html

Problem Description

Peanut owns a mushroom farm and wants to collect some mushrooms. His mushroom farm has N mushrooms in a row, numbered 0 to N-1 from left to right. Each mushroom i has deliciousness Di. He assigns M minions one by one to help him collect some mushrooms. Each minion i will be assigned a range A to B. However, each minion can only carry at most 1 mushroom, since they have small hands.

Each minion collects the mushroom with the highest deliciousness within the range. If there are multiple mushrooms of the same deliciousness, the minion collects the leftmost of the most delicious mushrooms. If the minion cannot collect any mushrooms, print -1. The collected mushroom is removed from the farm. Help peanut find the deliciousness of the mushrooms collected by each minion.

Input

The first line contains the number N and M.

The second line contains N numbers, representing the array D.

M lines will follow. Each line has 2 integers, A and B, representing the minion i query.

Output

For each line of query, you are to output the maximum number of mushrooms collected on a single line.

Limits

For all subtasks: 0 ≤ A ≤ B < N, 0 ≤ Di ≤ 109

Subtask 1 (34%): 1 ≤ N, M ≤ 2000.

Subtask 2 (66%): 1 ≤ N, M ≤ 200000.

Subtask 3 (0%): Sample Testcases.

Sample Input 1

5 5
3 1 4 2 5
0 1
2 4
1 2
2 4
2 3

Sample Output 1

3
5
4
2
-1

Explanation

Farm has initial mushroom values: 3 1 4 2 5
Minion 0 picks mushroom at position 0.
Minion 1 picks mushroom at position 4.
Minion 2 picks mushroom at position 2.
Minion 3 picks mushroom at position 3.
Minion 4 has no mushrooms to pick.

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
134211s256MBMinimum
266411s256MBMinimum
3011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o collectmushrooms2 -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.