C - Build Stairs

Contest Duration: 2019-08-04(Sun) 12:00 - 2019-08-04(Sun) 13:40 (local time) (100 minutes) Back to Home

C - Build Stairs Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $300$ 点

問題文

左右一列に $N$ 個のマスが並んでおり、左から $i$ 番目のマスの高さは $H_i$ です。

あなたは各マスについて $1$ 度ずつ次のいずれかの操作を行います。

マスの高さを $1$ 低くする。
何もしない。

操作をうまく行うことでマスの高さを左から右に向かって単調非減少にできるか求めてください。

制約

入力は全て整数である。
$1 \leq N \leq 10^5$
$1 \leq H_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $H_1$   $H_2$   $...$   $H_N$

出力

マスの高さを左から右に向かって単調非減少にできるなら Yes、そうでないなら No を出力せよ。

入力例 1Copy

Copy

5
1 2 1 1 3

出力例 1Copy

Copy

Yes

左から $2$ 番目のマスのみ高さを $1$ 低くすることで目的を達成できます。

入力例 2Copy

Copy

4
1 3 2 1

出力例 2Copy

Copy

No

入力例 3Copy

Copy

5
1 2 3 4 5

出力例 3Copy

Copy

Yes

入力例 4Copy

Copy

1
1000000000

出力例 4Copy

Copy

Yes

Score : $300$ points

Problem Statement

There are $N$ squares arranged in a row from left to right. The height of the $i$ -th square from the left is $H_i$ .

For each square, you will perform either of the following operations once:

Decrease the height of the square by $1$ .
Do nothing.

Determine if it is possible to perform the operations so that the heights of the squares are non-decreasing from left to right.

Constraints

All values in input are integers.
$1 \leq N \leq 10^5$
$1 \leq H_i \leq 10^9$

Input

Input is given from Standard Input in the following format:

 $N$ 
 $H_1$   $H_2$   $...$   $H_N$

Output

If it is possible to perform the operations so that the heights of the squares are non-decreasing from left to right, print Yes; otherwise, print No.

Sample Input 1Copy

Copy

5
1 2 1 1 3

Sample Output 1Copy

Copy

Yes

You can achieve the objective by decreasing the height of only the second square from the left by $1$ .

Sample Input 2Copy

Copy

4
1 3 2 1

Sample Output 2Copy

Copy

No

Sample Input 3Copy

Copy

5
1 2 3 4 5

Sample Output 3Copy

Copy

Yes

Sample Input 4Copy

Copy

1
1000000000

Sample Output 4Copy

Copy

Yes