RiseOJ – 눈 장화

설명

농장에 겨울이 왔고, 그것은 곧 눈을 의미한다! 농가에서 헛간으로 가는 길에는 $$N$$ 개의 타일이 있으며, 편의상 $1 \dots N$ 으로 번호가 매겨져 있고, 타일 $$i$$ 는 $$f_i$$ 피트 깊이의 눈으로 덮여 있다.

농가 지하실에 농부 존은 $1 \dots B$ 로 번호가 매겨진 $$B$$ 켤레의 장화를 가지고 있다. 어떤 켤레는 다른 것보다 더 튼튼하고, 어떤 켤레는 더 민첩하다. 구체적으로, $$i$$ 번째 켤레는 농부 존이 깊이 최대 $$s_i$$ 피트의 눈을 밟을 수 있게 해 주고, 한 걸음에 최대 $$d_i$$ 만큼 앞으로 나아갈 수 있게 해 준다.

농부 존은 타일 $$1$$ 에서 출발하여 소들을 깨우기 위해 타일 $$N$$ 에 도달해야 한다. 타일 $$1$$ 은 농가 지붕이, 타일 $$N$$ 은 헛간 지붕이 가려 주고 있으므로 이 두 타일에는 눈이 없다. 어떤 눈 장화 켤레들을 신으면 농부 존이 이 여정을 마칠 수 있는지 구하도록 도와주자.

출제자: Dhruv Rohatgi

제약

출제자: Dhruv Rohatgi

입력 형식

첫째 줄에 공백으로 구분된 두 정수 $$N$$ 과 $$B$$ 가 주어진다 ( $1 \leq N,B \leq 10^5$ ).

둘째 줄에 공백으로 구분된 정수 $$N$$ 개가 주어진다. $$i$$ 번째 정수는 타일 $$i$$ 위의 눈 깊이 $$f_i$$ 이다 ( $0 \leq f_i \leq 10^9$ ). $$f_1 = f_N = 0$$ 임이 보장된다.

다음 $$B$$ 개의 줄에는 각각 공백으로 구분된 정수 두 개가 주어진다. $$i+2$$ 번째 줄의 첫 번째 정수는 $$i$$ 번째 켤레로 밟을 수 있는 눈의 최대 깊이 $$s_i$$ 이다. $$i+2$$ 번째 줄의 두 번째 정수는 $$i$$ 번째 켤레의 최대 보폭 $$d_i$$ 이다. $0 \leq s_i \leq 10^9$ 이고 $1 \leq d_i \leq N-1$ 임이 보장된다.

출력 형식

출력은 $$B$$ 개의 줄로 이루어진다. $$i$$ 번째 줄에는 농부 존이 $$i$$ 번째 켤레의 장화를 신고 타일 $$1$$ 에서 타일 $$N$$ 까지 갈 수 있으면 $$1$$ , 그렇지 않으면 $$0$$ 을 나타내는 정수 하나를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 snowboots.in · 출력을 쓸 파일 snowboots.out

예제 1

입력

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

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > February > Gold

올림피아드 > USACO > 2017-2018 > February > Gold

태그

JudgeUSACO

눈 장화

평가 및 의견

풀이 제출