codeforces-scrape

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

1760D.md (2109B)


      1 Source: https://codeforces.com/problemset/problem/1760/D
      2 
      3 D. Challenging Valleys
      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 an array $a[0 \dots n-1]$ of $n$ integers. This array is called a "valley" if there exists exactly one subarray $a[l \dots r]$ such that:
     22 
     23 * $0 \le l \le r \le n-1$,
     24 * $a_l = a_{l+1} = a_{l+2} = \dots = a_r$,
     25 * $l = 0$ or $a_{l-1} \gt a_{l}$,
     26 * $r = n-1$ or $a_r \lt a_{r+1}$.
     27 
     28 Here are three examples:
     29 
     30  ![](https://espresso.codeforces.com/458aaea1b8f2c30d221cb47953593a0ba474452e.png) 
     31 
     32 The first image shows the array [$3, 2, 2, 1, 2, 2, 3$], it is a valley because only subarray with indices $l=r=3$ satisfies the condition.
     33 
     34 The second image shows the array [$1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 6$], it is a valley because only subarray with indices $l=0, r=2$ satisfies the codition.
     35 
     36 The third image shows the array [$1, 2, 3, 4, 3, 2, 1$], it is not a valley because two subarrays $l=r=0$ and $l=r=6$ that satisfy the condition.
     37 
     38 You are asked whether the given array is a valley or not.
     39 
     40 Note that we consider the array to be indexed from $0$.
     41 
     42 Input
     43 
     44 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     45 
     46 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the array.
     47 
     48 The second line of each test case contains $n$ integers $a_i$ ($1 \leq a_i \leq 10^9$) — the elements of the array.
     49 
     50 It is guaranteed that the sum of $n$ over all test cases is smaller than $2\cdot10^5$.
     51 
     52 Output
     53 
     54 For each test case, output "YES" (without quotes) if the array is a valley, and "NO" (without quotes) otherwise.
     55 
     56 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
     57 
     58 Example
     59 
     60 Input
     61 
     62 ```
     63 6
     64 
     65 7
     66 
     67 3 2 2 1 2 2 3
     68 
     69 11
     70 
     71 1 1 1 2 3 3 4 5 6 6 6
     72 
     73 7
     74 
     75 1 2 3 4 3 2 1
     76 
     77 7
     78 
     79 9 7 4 6 9 9 10
     80 
     81 1
     82 
     83 1000000000
     84 
     85 8
     86 
     87 9 4 4 5 9 4 9 10
     88 ```
     89 
     90 Output
     91 
     92 ```
     93 YES
     94 YES
     95 NO
     96 YES
     97 YES
     98 NO
     99 ```
    100 
    101 Note
    102 
    103 The first three test cases are explained in the statement.