Alien Guitar Performance
Time limit1sMemory limit256 MB
Simulate finger presses and releases on a 6-string guitar to play a melody in order with minimum total finger movements, keeping only pressed frets that could still be the highest useful one.
- Level
Medium7 of 10
- Topics
- Stack, Greedy, Simulation
- Solved
- No attempts yet
Problem
An alien with many fingers wants to play a given melody on a guitar.
The guitar has six strings, numbered from 1 to 6, and each string has frets numbered from 1 to P. A note is played by pressing a certain fret on a certain string and then plucking that string. If several frets are being pressed on the same string, the sound comes from the highest-numbered pressed fret.
For example, suppose fret 5 on string 3 is already being pressed. To play fret 7 on that string, the alien can keep pressing fret 5 and press fret 7 with another finger. To play fret 2 instead, the alien must release the fingers on frets 5 and 7, then press fret 2.
Pressing one fret once, or releasing one pressed fret once, counts as one finger movement. Given the melody in order, find the minimum number of finger movements needed to play it.
Input
The first line contains two integers N and P: the number of notes in the melody and the number of frets on each string. (1 <= N <= 500,000, 2 <= P <= 300,000)
Each of the next N lines contains two integers s and f describing one note. s is the string number, and f is the fret number that must be pressed on that string. The notes must be played in the order given. The string number is between 1 and 6, and the fret number is between 1 and P.
Output
Print the minimum number of finger movements needed to play the melody.