比赛场次 618
比赛名称 2024暑假C班集训8
比赛状态 已结束比赛成绩
开始时间 2024-07-08 08:00:00
结束时间 2024-07-08 12:00:00
开放分组 全部用户
注释介绍 难度:T2<[T3,T4]<T1
题目名称 吉他
输入输出 gitara.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar┭┮﹏┭┮ AAAAAAAAAA 0.101 s 2.87 MiB 100
Gravatardream AAAAAAAAAA 0.103 s 2.94 MiB 100
GravatardarkMoon AAAAAAAAAA 0.352 s 7.02 MiB 100
Gravatarwdsjl AAAAAAAAAA 0.375 s 2.87 MiB 100
Gravatar小金 AAAAAAAAAA 0.388 s 2.87 MiB 100
Gravatarliuyiche AAAAAAAAAA 0.429 s 2.94 MiB 100
Gravatar蜀山鸭梨大 AAAAAAAAAA 0.758 s 2.87 MiB 100
Gravatar彭欣越 AAAAAAAAAA 0.782 s 2.87 MiB 100
Gravatarflyfree AAAAAAAAAA 0.814 s 2.87 MiB 100
GravatarUntitled AAAAAATTTT 4.065 s 6.87 MiB 60
Gravatar陆晨洗 AAAAAATTTT 4.205 s 10.31 MiB 60
Gravatarwzh0425 AAAAATTTTT 5.004 s 5.62 MiB 50
GravatarKKZH AWAWAWTTTT 4.132 s 5.16 MiB 30
Gravatardjyqjy WWWWWWWWWW 3.493 s 3.44 MiB 0

吉他

★   输入文件:gitara.in   输出文件:gitara.out   简单对比
时间限制:1 s   内存限制:128 MiB

  (gitara.pas/c/cpp) 

【问题描述】

x有一个神密的朋友: 一个外星人,这个外星人有无数个触角,还有一把很神奇的吉他。小x最近一个爱好就是听外星人弹吉他。

这个吉他和非常巨大,有6根弦,每根弦有P品丝,编号为1..P,每根弦的每个品丝可以发出不同的乐音,且乐音的音调随着品丝的编号依次增加。

因为外星人有无数个触角,他可以触动很多个不同的品丝,来发出不同的乐音。这个吉他的神奇之处在于,如果外星人触动某根弦上多个品丝,它只会发出音调最高的乐音(品丝编号最高发出的乐音)。

现在,小x想让外星人朋友弹一首包含N个乐音的曲子,而外星人朋友则想让小x首先计算出他最少移动多少次触角能够完成这首曲子的弹奏。

【输入】

第一行包含两个整数:NP,表示曲子有N个乐音,吉他的每根弦上有P个品丝。

接下来N行,每行两个整数xiyi,表示第i个乐音需要触动第xi跟弦上的第yi个品丝。

【输出】

一个整数,表示最小的移动触角的次数。

【输入输出样例1

gitara.in

gitara.out

5 15

2 8

2 10

2 12

2 10

2 5

7

【样例解释】 第一个乐音需要移动1次触角,第二个也是1次,第三个也是1次,第四次需要把编号为12的品丝松开,也是1次,第5次需要把编号为8,10的品丝松开,并触动编号为5的品丝,需要3次。所以一共是7次。 

【输入输出样例2

gitara.in

gitara.out

7 15

1 5

2 3

2 5

2 7

2 4

1 5

1 3

9

【样例解释】依次移动触角的次数是:1, 1, 1, 1, 3, 0, 2

大样例:data

【数据范围】 

   50% 数据保证 0<=N,P<=5000

   100% 数据保证  0<=N<=500000   0<=P<=300000.