Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKLINEUP - Xếp hàng

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274824/problem/M

Hàng ngày khi lấy sữa, N con bò của bác John (1 ≤ N ≤ 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 ≤ Q ≤ 200000) đoạn các con bò và chiều cao của chúng (trong phạm vi [1, 1000000]). 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!

Dữ liệu

  • 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 ≤ A ≤ B ≤ N), cho biết đoạn các con bò từ A đến B.

Kết qủa

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.

Ví dụ

Dữ liệu:
6 3
1
7
3
4
2
5
1 5
4 6
2 2

Kết qủa
6
3
0

Được gửi lên bởi:Jimmy
Ngày:2007-12-15
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED
Nguồn bài:USACO JAN07 - Gold Division

hide comments
2013-12-16 16:19:18 Xiao Lang
Cây IT là cây phân đoạn. 1 dãy số sẽ phân làm các khúc quản lý từng đoạn một. Tư tưởng cây IT có thể tham khảo google
2013-12-12 04:22:12 Nguyễn Trọng Ðoan
mình ko hiểu cái IT này ai chỉ dùm mình đc ko vậy :((
2013-12-11 13:17:41 Xiao Lang
IT là AC
2013-11-20 13:48:37 Quốc Thắng
Phạm Văn Huân IT là Interval Tree hay còn gọi là Segment Tree.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
2013-11-16 13:30:49 Xứ Nẫu
nèy cũng 40.
2013-10-30 10:50:07 Phạm Vãn Huân
IT là thuật toán gì vậy các bạn. Các bạn viết tắt mình không hiểu?

Last edit: 2013-10-30 10:50:25
2013-10-23 16:38:13 hoa
cho mình hỏi, làm bất cứ bài nào trên này thì dữ liệu đều được nhập từ bàn phìm và in ra màn hình ah, chứ không phải nhận từ tệp đúng ko?
2013-07-21 05:02:31 Doraemon Grapes
IT AC được bài này
2013-06-17 13:22:31 Vũ Vãn Thành
IT dc 100 nhá
2013-04-20 17:27:47 [KC]★★★★ - darkmagician
sao dc co40d zay
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.