No.3611 Omega Cat (Judging ver.)
タグ : / 解いたユーザー数 54
作問者 :
kazuppa
/ テスター :
Problem Statement
$N$ cats are standing in a row. The $i$-th cat is the $i$-th from the left and has height $H_i$. It is guaranteed that the heights of all the cats are distinct.
Determine whether these cats satisfy the following condition.
- There exist integers $(x,y,z)$ satisfying all of the following conditions.
- $1< x< y< z< N$
- For every $i$ satisfying $1\leq i< x$, $H_i> H_{i+1}$
- For every $i$ satisfying $x\leq i< y$, $H_i< H_{i+1}$
- For every $i$ satisfying $y\leq i< z$, $H_i> H_{i+1}$
- For every $i$ satisfying $z\leq i< N$, $H_i< H_{i+1}$
You are given $T$ test cases; solve all of them.
Constraints
- $1\leq T\leq 4\times 10^4$
- $5\leq N\leq 2\times 10^5$
- $1\leq H_i\leq 10^9\ (1\leq i\leq N)$
- $H_i\neq H_j\ (i\neq j)$
- The sum of $N$ over all test cases is at most $2\times 10^5$
- All input values are integers
Subtasks
This problem has partial scoring by subtasks.
| Subtask | Points | Constraints |
|---|---|---|
| Subtask 1 | 30 points | $N=5$ |
| Subtask 2 | 60 points | $N\leq100,$ the sum of $N$ over all test cases is at most $100$ |
| Subtask 3 | 60 points | No additional constraints |
Input
$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
Each test case is given in the following format.
$N$ $H_1\ H_2\ \ldots\ H_N$
Output
Output $T$ lines.
On line $i\ (1\leq i\leq T)$, output Yes if the sequence $H$ given in the $i$-th test case satisfies the condition, and No otherwise.
Sample
Sample 1
Input
3 9 9 8 1 2 7 6 3 4 5 5 16 9 2 3 1 8 2 1 5 6 7 8 3 4
Output
Yes No Yes
For the 1st test case, the condition can be satisfied by choosing $(x,y,z)=(3,5,7)$.
For the 2nd test case, no $(x,y,z)$ satisfying the condition exists.
This input satisfies the constraints of Subtasks 2,3.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。