Олимпиадный тренинг

Задача . Why Did the Cow Cross the Road III


Задача

Темы:
Фермер Джон продолжает исследование переходов коров через дорогу, описанную в двух предыдущих задачах. Теперь он считает дружественными породы коров \(a\) и \(b\), если if \(|a - b| \leq K\), и недружественными в противном случае.

По заданному упорядочению пород на каждой из сторон дороги, определите количество недружественных пересекающихся пар пород, где пересекающиеся пары пород определены в предыдущей задаче.

ФОРМАТ ВВОДА (файл friendcross.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100,000\)) и \(K\) (\(0 \leq K < N\)). Следующие \(N\) строк описывают порядок по номерам пород, полей на первой стороне дороги. Каждый номер породы - это число в интервале \(1 \ldots N\). Последние \(N\) строк описывают порядок по номерам пород, полей на второй стороне дороги. Каждый номер породы появится ровно один раз с каждом порядке.

ФОРМАТ ВВОДА (файл friendcross.out):

Выведите максимальное количество недружественных пересекающихся пар пород.


Примеры
№Входные данныеВыходные данные
1 
ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ
 
1
2 
4
3
2
4
4
1
3
2
1
 
3
3 
3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3
 
2
4 
3
2 1
8 3
5 7
 
15
5 
8
3 1
3 0
6 0
2 1
4 1
3 0
4 0
3 1
 
3
6 
4 1
4
3
2
1
1
4
2
3
 
2
7 
5 4
7
8
6
2
9
2 5
4 9
0 3
8 13
 
3
8 
10 6 5
2
10
1
5
9
 
1
9 
5
5
4
1
3
2
1
3
2
5
4
 
0
10 
6
1
2
3
4
5
6
6
5
4
3
2
1
 
5
11 
6
1
2
3
4
5
6
6
5
4
3
2
1
 
5
12 
4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 80
 
31

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет