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 \(a\) and \(b\) are now friendly if \(|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.

Problem credits: Brian Dean

Problem credits: Brian Dean

The first line of input contains \(N\) (\(1 \leq N \leq 100,000\)) and \(K\)
(\(0 \leq 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 \ldots 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.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Platinum