#PU722. USACO 2017 February Contest, Platinum — Problem 3. Why Did the Cow Cross the Road III

    ID: 1373 传统题 文件IO:friendcross 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb17来源:usaco.orgscoring:equal_test_cases差分

USACO 2017 February Contest, Platinum — Problem 3. Why Did the Cow Cross the Road III

USACO 2017 February Contest, Platinum — Problem 3. Why Did the Cow Cross the Road III

题目描述

Farmer John is continuing to ponder the issue of cows crossing the road through his farm, introduced in the preceding two problems. He realizes now that the threshold for friendliness is a bit more subtle than he previously considered -- breeds aa and bb are now friendly if ∣a−b∣≤K|a - b| \leq K, and unfriendly otherwise. Given the orderings of fields on either side of the road through FJ's farm, please count the number of unfriendly crossing pairs of breeds, where a crossing pair of breeds is defined as in the preceding problems.

输入格式

The first line of input contains NN (1≤N≤100,0001 \leq N \leq 100,000) and KK (0≤K<N0 \leq K < N). The next NN lines describe the order, by breed ID, of fields on one side of the road; each breed ID is an integer in the range 1…N1 \ldots N. The last NN lines describe the order, by breed ID, of the fields on the other side of the road. Each breed ID appears exactly once in each ordering.

输出格式

Please output the number of unfriendly crossing pairs of breeds.

数据范围

(见题面原文)

样例

样例 1

4 1
4
3
2
1
1
4
2
3
2
In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.
Problem credits: Brian Dean