Informatica Online Judge

  스노우 부츠(Gold) [2183 / 0887]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 6   Total Tried : 12


The Champion of this Problem (C++) : gs16103 - 0ms / 1371byte
My Best Submission (C++) : N/A

[USACO 2018(Dhruv Rohatgi)]

Background

겨울이 와서, 존의 농장에 많은 눈이 내렸다.

존의 농가에서 젖소 축사까지에는 $N$개의 타일이 있는데, 편의상 각각의 타일 번호를 $1$, $2$, ..., $N$ 라고 할 때, 각 타일 위에는 $f_i$ 피트의 눈이 쌓여있다.

존의 농가 지하실에는 $1$, $2$, ..., $N$ 까지의 번호가 붙여진 $B$ 쌍의 부츠가 있다. 어떤 부츠들은 다른 부츠들보다 좋고, 어떤 부츠들은 다른 부츠들보다 좋지 않다.
$i$번째 부츠를 이용하면 최대 $s_i$피트 깊이까지 버틸 수 있으며, 한 걸음 뛸 때마다 최대 $d_i$ 칸 앞으로 이동할 수 있다.

농부 존은 젖소들을 깨우기 위해, 1번 타일에서 움직이기 시작해서 N번 타일까지 이동해야한다.
1번 타일은 농부존의 농가 지붕 아래에 있고, N번 타일은 축사 지붕 아래에 있기 때문에 눈이 전혀 쌓여있지 않다.

축사로 가는데 사용할 수 있는 부츠들을 알아내보자.

Input

첫 번째 줄에 $N$과 $B$가 공백을 두고 입력된다.
두 번째 줄에는 $N$개의 정수가 공백을 두고 입력된다.; i번째 정수는 각 타일에 쌓여있는 눈의 깊이인 $f_i$를 의미한다. $f_1$과 $f_N$은 0이다.
그 다음 B개의 줄에는 $s_i$와 $d_i$가 공백을 두고 입력된다.

[입력값의 정의역]
$1≤N, B≤100,000$
$0≤f_i≤1,000,000,000$
$f_1, f_N = 0$
$0≤s_i≤1,000,000,000$
$1≤d_i≤N-1$

Output

$1$번 부터 $B$번 부츠까지 축사로 도달할 수 있는지의 여부를, $1$(도달가능) 또는 $0$(도달 불가능)으로 줄을 바꿔 출력한다.

IO Example

입력
8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7

출력
0
1
1
0
1
1
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]