A2787. 跑圈数
编程题
普及+/提高
知识点
题目描述
农夫约翰让他的 n （1 <= n <= 100,000） 头牛在长度为 c 的跑道上进行跑 l 圈的比赛，所有牛从同一起点，以不同的速度开始跑。直到当跑得最快的那一头牛跑完 l 圈时，所有牛才同时停下。
约翰发现在跑圈过程中发生了几次“超越事件”。其定义是：在比赛结束前某时刻，奶牛 x 已经超越了奶牛 y **整整一圈**，则称做一次“超越事件”。（注： **至少一圈** ，超越了1/2圈，或者超越了1/4圈等等都不算。且对于同一对奶牛（x，y）不会重复计算次数。）
约翰想知道比赛过程中发生了多少次“超越事件”。
约翰发现在跑圈过程中发生了几次“超越事件”。其定义是：在比赛结束前某时刻，奶牛 x 已经超越了奶牛 y **整整一圈**，则称做一次“超越事件”。（注： **至少一圈** ，超越了1/2圈，或者超越了1/4圈等等都不算。且对于同一对奶牛（x，y）不会重复计算次数。）
约翰想知道比赛过程中发生了多少次“超越事件”。
输入格式
第一行：三个整数：n，l，c（1 <= l,c <= 25,000)
第二行到第 n+1 行：每行一个整数 vi ，表示奶牛i的速度（1 <= vi <= 1,000,000）
第二行到第 n+1 行：每行一个整数 vi ，表示奶牛i的速度（1 <= vi <= 1,000,000）
输出格式
第一行：一个整数，表示总共发生的“超越事件”的次数
输入输出样例
输入 #1
4 2 100 20 100 70 1
输出 #1
4
说明/提示
有 4 头奶牛在长度为 100 的圆形跑道上跑 2 圈。奶牛的速度分别为 20、100、70 和 1。
比赛持续 2 个单位的时间，因为这是最快的奶牛（奶牛 2）完成的时间。在这段时间内，有 4 个交叉事件：奶牛 2 超越奶牛 1 和 4，奶牛 3 超越奶牛 1 和 4。
比赛持续 2 个单位的时间，因为这是最快的奶牛（奶牛 2）完成的时间。在这段时间内，有 4 个交叉事件：奶牛 2 超越奶牛 1 和 4，奶牛 3 超越奶牛 1 和 4。