#PU493. USACO 2014 December Contest, Silver — Problem 3. Cow Jog

    ID: 1215 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:dec14来源:usaco.orgscoring:equal_test_cases并查集排序

USACO 2014 December Contest, Silver — Problem 3. Cow Jog

USACO 2014 December Contest, Silver — Problem 3. Cow Jog

题目描述

Problem 3: Cow Jog [Mark Gordon, 2014]

The cows are out exercising their hooves again! There are N cows

jogging on an infinitely-long single-lane track (1 <= N <= 100,000).

Each cow starts at a distinct position on the track, and some cows jog

at different speeds.

With only one lane in the track, cows cannot pass each other. When a

faster cow catches up to another cow, she has to slow down to avoid

running into the other cow, becoming part of the same running group.

The cows will run for T minutes (1 <= T <= 1,000,000,000). Please

help Farmer John determine how many groups will be left at this time.

Two cows should be considered part of the same group if they are at

the same position at the end of T minutes.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 3

0 1

1 2

2 3

3 2

6 1
3