COCI 2020/2021 - Contest 6 - Index
Xem dạng PDF
Gửi bài giải
Điểm:
1,50 (OI)
Giới hạn thời gian:
2.5s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Người đăng:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Chỉ số H (h-index) là chỉ số đánh giá dựa trên năng suất và số trích dẫn các bài báo của các học giả và nhà nghiên cứu. Chỉ số H được định nghĩa là giá trị ~H~ lớn nhất sao cho tác giả ấy có ít nhất ~H~ bài báo, mà mỗi bài được trích dẫn ít nhất ~H~ lần.
Giáo sư Mirko sắp nghỉ hưu. Suốt sự nghiệp, ông đã đăng ~N~ bài báo đánh số từ ~1~ đến ~N~. Ông tự hỏi rằng: giả như ông chỉ đăng các bài báo từ ~L~ đến ~R~ thì chỉ số H của ông sẽ là bao nhiêu?
Hãy giúp giáo sư trả lời câu hỏi trên ~Q~ lần.
Input
- Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ (~N, Q \leq 200000~).
- Dòng tiếp theo chứa ~N~ số nguyên dương ~P_i~ (~P_i \leq 200000~) là số trích dẫn của bài báo thứ ~i~.
- ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L~ và ~R~ (~1 \leq L \leq R \leq N~) cho câu hỏi của giáo sư Mirko.
Output
In ra ~Q~ dòng, mỗi dòng là đáp án cho câu hỏi của giáo sư với hai tham số tương ứng.
Ví dụ
Sample input
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
Sample output
1
3
3
1
2
2
Subtask
- ~N, Q \leq 1000~ (10 test)
- ~N, Q \leq 50000~ (10 test)
- Không có giới hạn gì thêm (10 test)
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.