Minimum Distance
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
5.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Dế Mèn có mảng ~a~ gồm ~n~ số nguyên. Anh ấy cần trả lời ~q~ truy vấn sau:
- ~l\ r~: Tìm cặp ~(i, j)~ ~(l \le i < j \le r)~ sao cho ~|a_i - a_j|~ nhỏ nhất có thể, in ra giá trị đó.
Tất nhiên Dế Mèn biết bài này giải bằng chia căn cơ bản, nhưng Dế Mèn đang lười nên các bạn code giúp nhé!
Input
- Dòng đầu gồm số nguyên dương ~n~ là độ dài mảng ~a~ ~(2 \le n \le 10^5)~.
- Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^9)~.
- Dòng thứ ba gồm số nguyên dương ~q~ là số truy vấn cần trả lời (~1 \le q \le 3 \cdot 10^5~).
- ~q~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~l, r~ tương ứng với một truy vấn ~(1 \le l < r \le n)~.
Output
In ra ~q~ dòng tương ứng câu trả lời cho ~q~ truy vấn.
Sample Input 1
8
3 1 4 1 5 9 2 6
4
1 8
1 3
4 8
5 7
Sample Output 1
0
1
1
3
Bình luận
Thuật nhanh nhất cho bài này: thuật chuẩn của 1793F. Điều kiện hoán vị của 1793F thực ra không quan trọng, nhưng sẽ khó cài hơn một chút.
bạn có thể hướng dẫn cho mình thuật bài này làm như nào không ?