Shuffle (Codeforces 1366B)
Tags: Math, two pointers

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$$$.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$$$.Calculate the number of indices $$$k$$$ such that it is possible to choose the operations so that $$$a_k = 1$$$ in the end.

Input: 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.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$$$).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$$$).

Output: 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.

Note: 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:  swap $$$a_k$$$ and $$$a_4$$$;  swap $$$a_2$$$ and $$$a_2$$$;  swap $$$a_5$$$ and $$$a_5$$$. 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.

Sample Inputs:
3
6 4 3
1 6
2 3
5 5
4 1 2
2 4
1 2
3 3 2
2 3
1 2

Sample Outputs:
6
2
3

Solution (Python):
R = lambda : map(int, input().split())
(t,) = R()
for _ in [0] * t:
    (n, x, m) = R()
    y = x
    for _ in [0] * m:
        (l, r) = R()
        if y >= l and r >= x:
            x = min(x, l)
            y = max(y, r)
    print(y - x + 1)

Solution (Python):
R = lambda : map(int, input().split())
(t,) = R()
for _ in [0] * t:
    (n, x, m) = R()
    y = x
    for _ in [0] * m:
        (l, r) = R()
        if y >= l and r >= x:
            x = min(x, l)
            y = max(y, r)
    print(y - x + 1)

Solution (Python):
R = lambda : map(int, input().split())
(t,) = R()
for _ in [0] * t:
    (n, x, m) = R()
    y = x
    for _ in [0] * m:
        (l, r) = R()
        if y >= l and r >= x:
            x = min(x, l)
            y = max(y, r)
    print(y - x + 1)