codeforces-scrape

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

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$.