Xếp hàng

View as PDF

Submit solution


Points: 0.07 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO January 2007 - Gold Division
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hàng ngày khi lấy sữa, ~N~ con bò của bác John (~1~ ~\leq~ ~N~ ~\leq~ ~50000~) luôn xếp hàng theo thứ tự không đổi. Một hôm bác John quyết định tổ chức một trò chơi cho một số con bò. Để đơn giản, bác John sẽ chọn ra một đoạn liên tiếp các con bò để tham dự trò chơi. Tuy nhiên để trò chơi diễn ra vui vẻ, các con bò phải không quá chênh lệch về chiều cao.

Bác John đã chuẩn bị một danh sách gồm ~Q~ (~1~ ~\leq~ ~Q~ ~\leq~ ~200000~) đoạn các con bò và chiều cao của chúng (trong phạm vi [~1~, ~10^6~]). Với mỗi đoạn, bác John muốn xác định chênh lệch chiều cao giữa con bò thấp nhất và cao nhất. Bạn hãy giúp bác John thực hiện công việc này!

Input

  • Dòng đầu tiên chứa ~2~ số nguyên ~N~ và ~Q~.
  • Dòng thứ ~i~ trong số ~N~ dòng sau chứa ~1~ số nguyên duy nhất, là độ cao của con bò thứ ~i~.
  • Dòng thứ ~i~ trong số ~Q~ trong tiếp theo chứa ~2~ số nguyên ~A~, ~B~ (~1~ ~\leq~ ~A~ ~\leq~ ~B~ ~\leq~ ~N~), cho biết đoạn các con bò từ ~A~ đến ~B~.

Output

Gồm ~Q~ dòng, mỗi dòng chứa ~1~ số nguyên, là chênh lệch chiều cao giữa con bò thấp nhất và cao nhất thuộc đoạn tương ứng.

Sample Input

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

Sample Output

6
3
0

Comments

Please read the guidelines before commenting.



  • -3
    khanhlani  commented on June 19, 2024, 12:54 p.m.

    Lyna mãi đỉnh


  • 10
    Marr_HH  commented on July 8, 2022, 2:27 p.m. edited

    bài này phải code 2 tree ạ?


    • 6
      LamTer  commented on July 9, 2022, 3:47 a.m.

      code 1 tree lấy cả min max luôn nha bạn


  • -157
    MinhMinhMinhMinh  commented on Dec. 17, 2021, 4:20 a.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 49
      leduykhongngu  commented on Dec. 17, 2021, 4:21 a.m.

      Bình luận của bạn mang tính spam và gây khiêu khích. Một lần nữa bạn sẽ bị cấm bình luận, nặng hơn là ban acc vĩnh viễn nhé.