2163C.md (3133B)
1 Source: https://codeforces.com/problemset/problem/2163/C 2 3 C. Monopati 4 5 time limit per test 6 7 2 seconds 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 a grid $a$ of $2$ rows and $n$ columns, where every cell has value from $1$ to $2n$. 22 23 Let $f(l, r)$, where $1 \le l \le r \le 2n$, represent a binary$^{\text{∗}}$ grid $b$ of $2$ rows and $n$ columns, such that $b_{i, j} = 1$ if and only if $l \le a_{i, j} \le r$. Note that cell $(i, j)$ denotes the cell $i$ rows from the top and $j$ columns from the left. 24 25 Count the number of pairs of integers $(l, r)$ such that $1 \le l \le r \le 2n$, and in $f(l, r)$ there exists a down-right path of adjacent cells$^{\text{†}}$ with value of $1$ from cell $(1, 1)$ to $(2, n)$. 26 27 $^{\text{∗}}$A grid is considered binary if and only if every cell of it has value of $\mathtt{0}$ or $\mathtt{1}$. 28 29 $^{\text{†}}$A down-right path of adjacent cells is a sequence of cells such that each cell in the sequence shares either its top side or its left side with a side of the previous cell in the sequence. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 34 35 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of columns in the grid. 36 37 The second line contains exactly $n$ integers $a_{1, 1}$, $a_{1, 2}$, ..., $a_{1, n}$ ($1 \le a_{1, i} \le 2n$) — the values of the cells of the first row of the grid. 38 39 The third line contains exactly $n$ integers $a_{2, 1}$, $a_{2, 2}$, ..., $a_{2, n}$ ($1 \le a_{2, i} \le 2n$) — the values of the cells of the second row of the grid. 40 41 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 42 43 Output 44 45 For every test case, output on a separate line a single integer representing the number of pairs of integers $(l, r)$ such that $1 \le l \le r \le 2n$, and in $f(l, r)$ there exists a down-right path of adjacent cells with value of $1$ from cell $(1, 1)$ to $(2, n)$. 46 47 Example 48 49 Input 50 51 ``` 52 5 53 54 2 55 56 1 3 57 58 3 1 59 60 3 61 62 1 2 3 63 64 3 2 1 65 66 4 67 68 1 5 5 5 69 70 5 3 1 2 71 72 4 73 74 8 8 8 8 75 76 8 8 8 8 77 78 6 79 80 6 6 5 7 9 12 81 82 1 4 2 8 5 6 83 ``` 84 85 Output 86 87 ``` 88 2 89 90 5 91 92 4 93 94 8 95 96 25 97 ``` 98 99 Note 100 101 Consider the first example. 102 103 The grids $f(1, 1), f(1, 2)$ will look like the following: 104 105 $$ \mathtt{10} $$ $$ \mathtt{01} $$ 106 107 There does not exist a path of $1$s from the top-left cell to the bottom-right cell, therefore the pairs $(1, 1)$ and $(1, 2)$ are not counted. 108 109 The grids $f(1, 3)$ and $f(1, 4)$ will look like the following: 110 111 $$ \mathtt{11} $$ $$ \mathtt{11} $$ 112 113 Since there exists a valid path from $(1, 1)$ to $(2, 2)$, the pairs $(1, 3)$ and $(1, 4)$ will be counted. 114 115 The grids $f(2, 2)$, $f(4, 4)$ will be the following: 116 117 $$ \mathtt{00} $$ $$ \mathtt{00} $$ 118 119 The grids $f(2, 3)$, $f(2, 4)$, $f(3, 3)$, $f(3, 4)$ will look like the following: 120 121 $$ \mathtt{01} $$ $$ \mathtt{10} $$ 122 123 So the pairs $(2, 3)$, $(2, 4)$, $(3, 3)$ and $(3, 4)$ will not be counted. 124 125 The only pairs counted where pairs $(1, 3)$ and $(1, 4)$, so the answer is $2$.