1366B.md (1733B)
1 Source: https://codeforces.com/problemset/problem/1366/B 2 3 B. Shuffle 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array consisting of $n$ integers $a_1$, $a_2$, ..., $a_n$. Initially $a_x = 1$, all other elements are equal to $0$. 22 23 You have to perform $m$ operations. During the $i$-th operation, you choose two indices $c$ and $d$ such that $l_i \le c, d \le r_i$, and swap $a_c$ and $a_d$. 24 25 Calculate the number of indices $k$ such that it is possible to choose the operations so that $a_k = 1$ in the end. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Then the description of $t$ testcases follow. 30 31 The first line of each test case contains three integers $n$, $x$ and $m$ ($1 \le n \le 10^9$; $1 \le m \le 100$; $1 \le x \le n$). 32 33 Each of next $m$ lines contains the descriptions of the operations; the $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$). 34 35 Output 36 37 For each test case print one integer — the number of indices $k$ such that it is possible to choose the operations so that $a_k = 1$ in the end. 38 39 Example 40 41 Input 42 43 ``` 44 3 45 6 4 3 46 1 6 47 2 3 48 5 5 49 4 1 2 50 2 4 51 1 2 52 3 3 2 53 2 3 54 1 2 55 ``` 56 57 Output 58 59 ``` 60 6 61 2 62 3 63 ``` 64 65 Note 66 67 In the first test case, it is possible to achieve $a_k = 1$ for every $k$. To do so, you may use the following operations: 68 69 1. swap $a_k$ and $a_4$; 70 2. swap $a_2$ and $a_2$; 71 3. swap $a_5$ and $a_5$. 72 73 In the second test case, only $k = 1$ and $k = 2$ are possible answers. To achieve $a_1 = 1$, you have to swap $a_1$ and $a_1$ during the second operation. To achieve $a_2 = 1$, you have to swap $a_1$ and $a_2$ during the second operation.