codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.