A printable version of this contest can be found here.
The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered
from 1 to n. Each input represents one integer. Maximizer has one output which
represents the maximum value present on Maximizer's inputs.
Maximizer is implemented as a pipeline of sorters <!-- MATH
$Sorter(i_{1} , j_{1})$
-->
Sorter(i1, j1), ..., <!-- MATH
$Sorter(i_{k} , j_{k})$
-->
Sorter(ik, jk). Each
sorter has n inputs and n outputs. <!-- MATH
$Sorter(i, j)$
-->
Sorter(i, j) sorts values on inputs <!-- MATH
$i, i + 1, \dots, j$
-->
i, i + 1,..., j in non-decreasing
order and lets the other inputs pass through unchanged. The n-th output of the last sorter is the output of the
Maximizer.
An intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer
would still produce the correct result. What is the length of the shortest subsequence of
the given sequence of sorters in the pipeline still producing correct results for all possible combinations
of input values?
Task
Write a program that:
Input consists of several test case, each separated by a blank line. The first line of the file indicates the number of test cases, and it's followed by a blank line.
The first line of each test case contains two integers n and m <!-- MATH
$(2 \le n \le 50000, 1 \le m \le 500000)$
-->
(2
SRC="/ntujudge/problemdata/606.gif"
ALT="$ \le$">n
SRC="/ntujudge/problemdata/606.gif"
ALT="$ \le$">50000, 1
SRC="/ntujudge/problemdata/606.gif"
ALT="$ \le$">m
SRC="/ntujudge/problemdata/606.gif"
ALT="$ \le$">500000)
separated by a single space. Integer n is the number of inputs and integer m is the number of sorters
in the pipeline. The initial sequence of sorters is described in the next m lines. The k-th of these
lines contains the
parameters of the k-th sorter: two integers ik and jk <!-- MATH
$(1 \le i_{k} < j_{k} \le n)$
-->
(1
SRC="/ntujudge/problemdata/606.gif"
ALT="$ \le$">ik < jk
SRC="/ntujudge/problemdata/606.gif"
ALT="$ \le$">n)
by a single space.
The output consists of only one line containing an integer equal to the length of the shortest subsequence
of the initial sequence of sorters still producing correct results for all possible data.
Print a blank line between test cases.
1 40 6 20 30 1 10 10 20 20 30 15 25 30 40
4
Migrated from old NTUJ.
CEPC 2003
| No. | Testdata Range | Score |
|---|