問題一覧 > 通常問題

No.905 Sorted?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 204
作問者 : face4face4 / テスター : 37zigen37zigen
9 ProblemId : 3433 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-10-05 08:43:23

問題文

長さ$N$の整数列$A$と、そのindexの組$l$,$r$が与えられるので、部分列[$A_l, A_{l+1},\cdots,A_{r-1},A_r$]が
広義単調増加であるか、広義単調減少であるかをそれぞれ判定してください。

回答は、以下で定義される2つの関数$f(l, r), g(l, r)$の値をこの順番で空白区切りで出力することにより行ってください。
\begin{eqnarray} f(l, r)=\left\{ \begin{array}{ll} 1 & (部分列[A_l, A_{l+1},\cdots,A_{r-1},A_r]が広義単調増加である) \\ 0 & (上記以外) \\ \end{array} \right. \end{eqnarray} \begin{eqnarray} g(l, r)=\left\{ \begin{array}{ll} 1 & (部分列[A_l, A_{l+1},\cdots,A_{r-1},A_r]が広義単調減少である) \\ 0 & (上記以外) \\ \end{array} \right. \end{eqnarray}

この問題において、
列$A_0, ... A_k$が広義単調増加であるとは、すべての$0 \leq i < k$について$A_i \leq A_{i+1}$であることを、
列$A_0, ... A_k$が広義単調減少であるとは、すべての$0 \leq i < k$について$A_i \geq A_{i+1}$であることをそれぞれ指します。
ただし、長さ1の部分列は広義単調減少でも広義単調増加でもあるものとします。

なお、indexの組$l$,$r$は$Q$組与えられるので、そのすべてを処理してください。

入力

$N$
$A_0\ \cdots\ A_{N-1}$
$Q$
$l_0\ r_0$
$\vdots$
$l_{Q-1}\ r_{Q-1}$

入力は全て整数で与えられる。

  • $1 \leq N \leq 10^5$
  • $-10^{18} \leq A_i \leq 10^{18}$
  • $1 \leq Q \leq 10^5$
  • $0 \leq l_i \leq r_i \leq N-1$

出力

$Q$行出力してください。$i$行目には$f(l_i, r_i),g(l_i, r_i)$を空白区切りで出力して下さい。最後に改行してください。

サンプル

サンプル1
入力
5
8 -3 -4 0 9
3
0 1
1 3
2 4
出力
0 1
0 0
1 0
サンプル2
入力
5
10 10 10 9 9
3
0 0
0 2
2 4
出力
1 1
1 1
0 1
サンプル3
入力
4
-2 0 -2 -3
1
0 3
出力
0 0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。