No.905 Sorted?

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 119
作問者 : face4face4 / テスター : 37zigen37zigen
2 ProblemId : 3433 / 出題時の順位表

問題文

長さ$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
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。