COCI '10 Contest 7 #3 Gitara

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem types

Darko has a new imaginary extraterrestrial friend with a billion fingers. The extraterrestrial has soon taken hold of his guitar, found a simple melody online, and started playing it.

The guitar, as usual, has six strings denoted by numbers 1 through 6. Each string is divided into P frets denoted by numbers 1 through P.

A melody is a sequence of tones, where each tone is produced by picking a string pressed on a specific fret (e.g., 4^\text{th} string pressed on the 8^\text{th} fret). If a string is pressed on several frets, the produced tone will be the one corresponding to the highest of those frets.

For instance, if the 3^\text{rd} string is already pressed on the 5^\text{th} fret, and the tone which corresponds to the 7^\text{th} fret is to be produced, the string can be pressed on the 7^\text{th} fret and picked without releasing the 5^\text{th} fret, since only the highest one affects the tone produced (7^\text{th} in this case). Similarly, if a tone that corresponds to the 2^\text{nd} fret on the same string is next to be produced, it is necessary to release both 5^\text{th} and 7^\text{th} frets.

Write a program which computes the minimum number of finger movements needed to produce the given melody. Note that press or release a single fret counts as one finger move. String picking does not count as a finger move, but rather a guitar pick move.

Input Specification

The first line of input contains two positive integers separated by a single space, N (N \le 500\,000) and P (2 \le P \le 300\,000). They represent the number of tones in the melody and the number of frets, respectively.

The following N lines describe the fields for the corresponding tones – the ordinal of the string and the ordinal of the fret, respectively, in the same order as the extraterrestrial plays them.

Output Specification

In a single line of output, print the minimum number of finger movements.

Sample Input 1

5 15
2 8
2 10
2 12
2 10
2 5

Sample Output 1


Explanation for Sample Output 1

All the tones played are produced by picking the 2^\text{nd} string. First, the frets 8, 10, 12 are pressed, in order (three movements). Then, the 12^\text{th} fret is released to produce the second tone again (fourth movement). Finally, the 5^\text{th} fret is pressed followed by the release of frets 10 and 12 (a total of seven movements).

Sample Input 2

7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3

Sample Output 2


Explanation for Sample Output 2

1, 1, 1, 1, 3, 0, 2 finger movements are necessary, in the order of the seven tones produced.


There are no comments at the moment.