Why Did the Cow Cross the Road III

提交数: 6, 通过率: 33.33%, 平均分: 78.67

题目描述:

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 su
btle than he previously considered -- breeds aa and bb are now friendly if |a-b|≤K, and unfriendly 
otherwise.Given the orderings of fields on either side of the road through FJ's farm, please count t
he number of unfriendly crossing pairs of breeds, where a crossing pair of breeds is defined as in t
he preceding problems.

输入格式:

The first line of input contains N (1≤N≤100,000) and K (0≤K<N). 
The next N 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…N. The last N 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.

样例输入:

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.

时间限制: 1000ms
空间限制: 128MB

来源: Usaco2017 Feb Platinum