#5169. DIFFK - Hiệu số K

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một mảng A gồm N số nguyên đã được sắp xếp tăng dần và một số nguyên không âm K . Hãy đếm số lượng cặp chỉ số (i, j) thỏa mãn i < j A_j - A_i = K .

Dữ liệu:

  • Dòng đầu tiên chứa hai số nguyên N K\ (2 \le N \le 2 \cdot 10^5, 0 \le K \le 10^9) .
  • Dòng thứ hai chứa N số nguyên A_i\ (-10^9 \le A_i \le 10^9) của mảng.

Kết quả: Một số nguyên duy nhất là số lượng cặp tìm được.

Ví dụ:

Dữ liệu:

7 3
1 2 4 5 7 8 10

Kết quả:

4

Giải thích: Các cặp có hiệu bằng 3 là (1, 4), (2, 5), (4, 7), (5, 8).