Giao Nhau Của Những Người Bạn

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John có $N$ giống bò được đánh số từ $1$ đến $N$ . Mỗi giống bò xuất hiện đúng một lần ở mỗi bên của con đường. Hai giống bò $a$ và $b$ được gọi là không thân thiện nếu $| a - b | > K$ .

Một cặp giống bò $(a, b)$ được gọi là giao nhau nếu chúng xuất hiện theo thứ tự khác nhau ở hai bên đường. Cụ thể, nếu bò $a$ đứng trước bò $b$ ở bên trái, nhưng bò $b$ đứng trước bò $a$ ở bên phải, thì cặp này giao nhau.

Hãy đếm số cặp giống bò không thân thiện mà còn giao nhau.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ ( $1 \leq N \leq 100 000$ ) và $K$ ( $0 \leq K < N$ ).
$N$ dòng tiếp theo: Thứ tự xuất hiện của các giống bò ở bên trái đường (mỗi giống bò một dòng).
$N$ dòng tiếp theo: Thứ tự xuất hiện của các giống bò ở bên phải đường (mỗi giống bò một dòng).

Dữ liệu ra

Một số nguyên duy nhất là số cặp giống bò không thân thiện mà giao nhau.

Ràng buộc

$1 \leq N \leq 100 000$
$0 \leq K < N$
Mỗi giống bò từ $1$ đến $N$ xuất hiện đúng một lần ở mỗi bên đường.

Ví dụ

Input	Output	Giải thích
4 1 4 3 2 1 1 4 2 3	2	Với $K = 1$ , hai giống bò không thân thiện nếu hiệu của chúng $> 1$ . Bên trái: $4, 3, 2, 1$ . Bên phải: $1, 4, 2, 3$ . Cặp $(1, 4)$ : bên trái $4$ trước $1$ , bên phải $1$ trước $4$ → giao nhau. $\| 1 - 4 \| = 3 > 1$ → không thân thiện. ✓ Cặp $(1, 3)$ : bên trái $3$ trước $1$ , bên phải $1$ trước $3$ → giao nhau. $\| 1 - 3 \| = 2 > 1$ → không thân thiện. ✓ Cặp $(2, 4)$ : bên trái $4$ trước $2$ , bên phải $4$ trước $2$ → không giao nhau. Các cặp còn lại hoặc thân thiện ( $\| a - b \| \leq 1$ ) hoặc không giao nhau. Tổng: $2$ cặp.
100 3 58 65 97 79 8 68 16 81 37 56 5 83 31 47 84 89 69 21 85 90 98 87 39 61 71 30 54 28 96 1 3 27 82 18 43 7 59 12 2 100 19 23 38 88 11 10 4 93 44 48 52 76 86 66 40 6 45 34 22 46 49 33 78 72 92 32 51 77 94 64 80 53 24 14 57 91 41 73 36 35 70 63 17 75 26 25 62 15 9 74 55 60 13 99 95 20 67 50 29 42 17 60 91 65 83 39 36 74 90 30 4 27 13 2 16 94 53 28 56 98 11 20 23 95 49 46 96 26 100 3 48 19 59 68 8 76 89 67 87 12 73 24 54 63 61 25 57 78 85 21 1 99 79 42 70 93 75 7 51 37 72 81 82 34 97 18 71 35 40 58 77 52 33 10 88 6 62 84 41 69 22 43 38 86 55 92 47 15 64 50 31 9 66 29 32 14 5 80 45 44	2175	Với $N = 100$ , $K = 3$ , có $2175$ cặp giống bò không thân thiện mà giao nhau.

Ghi chú

Hai giống bò $a$ và $b$ là thân thiện nếu $| a - b | \leq K$ . Bài yêu cầu đếm số cặp vừa không thân thiện ( $| a - b | > K$ ) vừa giao nhau (xuất hiện theo thứ tự ngược nhau ở hai bên đường).

Bình luận

Không có bình luận tại thời điểm này.