페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8566
서브태스크

허수아비 2s 1024MB

문제

수직선의 위치 0에서 오른쪽 방향으로 힘 P 를 가진 화살이 발사된다.

각 정수 위치 i(1≤i≤N)에는 방어력 A_i 를 가진 허수아비를 최대 하나 설치할 수 있다.

화살이 허수아비에 부딪치면, 화살의 힘이 방어력보다 작거나 같을 경우 화살은 즉시 멈춘다.

반대로 화살의 힘이 방어력보다 크면, 화살의 힘은 현재 화살의 힘에서 Ai 만큼 줄어든 채 계속 진행한다.

정수 i에 대하여 f(i)의 값을 "화살이 위치 i에서 멈추거나 위치 i보다 왼쪽에서 멈추도록 하기 위해 필요한 허수아비의 최소 개수" 라고 정의하자.

화살을 멈추게 할 수 있는 방법이 없을 때의 값은 -1이다.

예를 들어서 N=5, P=10이고 A_1=3, A_2=6, A_3=1, A_4=1, A_5=10 이라고 하자.

모든 f(i)의 값과 설치한 허수아비의 위치는 다음과 같다.

i

f(i)값

설치한 허수아비의 위치

i=1

-1

불가능

i=2

-1

불가능

i=3

3

[1, 2, 3]

i=4

3

[1, 2, 3] 혹은 [1, 2, 4]중 하나 선택 가능

i=5

1

[5]

1 ≤i≤N인 모든 i에 대하여 f(i)의 값을 구하는 프로그램을 작성하라.

[제약 조건]

  • 주어지는 모든 수는 정수이다.

  • 1 ≤N≤500\,000

  • 1 ≤P≤10^9

  • 1 ≤i≤N 인 모든 i에 대하여 1≤A_i≤10^9


입력

첫 번째 줄에 정수 N과 화살의 힘 P 가 공백을 사이에 두고 주어진다.

두 번째 줄에 N개의 정수 A_1, A_2, ..., A_N이 공백을 사이에 두고 주어진다.


출력

첫 번째 줄에 f(1), f(2), ..., f(N)의 값을 공백을 사이에 두고 출력한다.


부분문제

번호 점수 조건
#14점

N≤8

#28점

N≤5\,000

#38점

1≤i≤N인 모든 i 에 대하여 A_i=1

#420점

1 ≤i≤N 인 모든 i 에 대하여 A_i=2 또는 A_i=3

#540점

1 ≤i≤N 인 모든 i 에 대하여 A_i≤50

#640점

1 ≤i≤N 인 모든 i 에 대하여 A_i≤A_{i+1}

#730점

추가 제약 조건 없음.


예제 #1

5 10
3 6 1 1 10
-1 -1 3 3 1

예제 #2

3 10
20 20 20
1 1 1


출처

2025 KOI 1차 초3
로그인해야 코드를 작성할 수 있어요.