루미 알고리즘

#1112골드건초 더미건초 더미

KOI 2025 1차코딩중등부 3번출제 오주원이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

건초 더미

원제: 건초 더미

문제

수직선의 위치 00에서 오른쪽 방향으로 정수 크기의 힘을 가진 화살이 발사된다. 각 정수 위치 ii (1≤i≤N)(1 \le i \le N)에는 방어력 DiD_i를 가진 건초 더미를 최대 하나 설치할 수 있다.

화살이 건초 더미에 부딪쳤을 때 화살의 힘이 방어력보다 작거나 같으면, 화살은 즉시 멈춘다. 반대로 화살의 힘이 방어력보다 크면, 힘이 방어력 DiD_i만큼 감소한 뒤 건초 더미를 관통해 계속 날아간다.

두 정수 XX, PP에 대하여 f(X,P)f(X, P)의 값을 "힘이 PP인 화살이 위치 XX에서 멈추거나 위치 XX보다 왼쪽에서 멈추도록 하기 위해 설치해야 하는 건초 더미의 최소 개수" 라고 정의하자. 만약 어떠한 설치 방법으로도 화살을 멈추게 할 수 있는 방법이 없다면, f(X,P)=−1f(X, P) = -1로 정의한다.

QQ개의 정수 쌍 (Xj,Pj)(X_j, P_j) (1≤j≤Q1 \le j \le Q)에 대해 각각 f(Xj,Pj)f(X_j, P_j)의 값을 구하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N,Q≤300 0001 \le N, Q \le 300\,000
  • 1≤i≤N1 \le i \le N인 모든 ii에 대하여 1≤Di≤1091 \le D_i \le 10^9
  • 1≤j≤Q1 \le j \le Q인 모든 jj에 대하여 1≤Xj≤N1 \le X_j \le N
  • 1≤j≤Q1 \le j \le Q인 모든 jj에 대하여 1≤Pj≤1091 \le P_j \le 10^9

부분문제

  1. (6점) N,Q≤18N, Q \le 18
  2. (16점) N,Q≤5 000N, Q \le 5\,000
  3. (18점) 1≤i≤N1 \le i \le N인 모든 ii에 대하여 Di≤300D_i \le 300
  4. (32점) 1≤i<N1 \le i < N인 모든 ii에 대하여 Di≤Di+1D_i \le D_{i+1}
  5. (28점) N=QN = Q, 1≤j≤Q1 \le j \le Q인 모든 jj에 대하여 Xj=jX_j = j, P1=P2=⋯=PQP_1 = P_2 = \cdots = P_Q
  6. (16점) 1≤j≤Q1 \le j \le Q인 모든 jj에 대하여 Xj=NX_j = N
  7. (12점) 1≤i<j≤N1 \le i < j \le N인 모든 i,ji, j에 대하여 Di≠DjD_i \ne D_j
  8. (22점) 추가 제약 사항 없음.

입력 형식

첫 번째 줄에는 건초 더미의 설치할 수 있는 위치의 개수 NN과 발사되는 화살의 횟수 QQ가 공백을 사이에 두고 주어진다.

두 번째 줄에는 위치 ii (1≤i≤N1 \le i \le N)에 놓을 수 있는 건초 더미의 방어력 D1,D2,⋯ ,DND_1, D_2, \cdots, D_N이 공백을 사이에 두고 주어진다.

세 번째 줄부터 QQ개의 줄에 걸쳐 QQ개의 정수 쌍이 주어진다. 이 중 jj (1≤j≤Q1 \le j \le Q) 번째 줄에는 XjX_j와 PjP_j가 공백을 사이에 두고 주어진다.

출력 형식

QQ개의 줄을 출력한다. 이 중 jj (1≤j≤Q1 \le j \le Q)번째 줄에는 f(Xj,Pj)f(X_j, P_j)의 값을 출력한다.

예제

예제 1

입력
5 6
2 5 6 1 12
1 1
5 14
2 8
3 7
4 14
5 1
출력
1
2
-1
2
4
1

예제 2

입력
5 5
3 6 1 1 10
1 10
2 10
3 10
4 10
5 10
출력
-1
-1
3
3
1

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.