건초 더미
플래티넘 II의견: 0
수직선의 위치 \(0\)에서 오른쪽 방향으로 정수 크기의 힘을 가진 화살이 발사된다. 각 정수 위치 \(i\) (\(1 ≤ i ≤ N\))에는 방어력 \(D_i\)를 가진 건초 더미를 최대 하나 설치할 수 있다.
화살이 건초 더미에 부딪쳤을 때 화살의 힘이 방어력보다 작거나 같으면, 화살은 즉시 멈춘다. 반대로 화살의 힘이 방어력보다 크면, 힘이 방어력 \(D_i\) 만큼 감소한 뒤 건초 더미를 관통해 계속 날아간다.
두 정수 \(X\), \(P\)에 대하여 \(f(X, P)\)의 값을 "힘이 \(P\)인 화살이 위치 \(X\)에서 멈추거나 위치 \(X\)보다 왼쪽에서 멈추도록 하기 위해 설치해야 하는 건초 더미의 최소 개수" 라고 정의하자. 만약 어떠한 설치 방법으로도 화살을 멈추게 할 수 있는 방법이 없다면, \(f(X, P) = −1\)로 정의한다.
\(Q\)개의 정수 쌍 \((X_j , P_j )\) (\(1 ≤ j ≤ Q\))에 대해 각각 \(f(X_j , P_j)\)의 값을 구하는 프로그램을 작성하라.
- 주어지는 모든 수는 정수이다.
- \(1 ≤ N, Q ≤ 300\, 000\)
- \(1 ≤ i ≤ N\)인 모든 \(i\)에 대하여 \(1 ≤ D_i ≤ 10^9\)
- \(1 ≤ j ≤ Q\)인 모든 \(j\)에 대하여 \(1 ≤ X_j ≤ N\)
- \(1 ≤ j ≤ Q\)인 모든 \(j\)에 대하여 \(1 ≤ P_j ≤ 10^9\)
첫 번째 줄에는 건초 더미의 설치할 수 있는 위치의 개수 \(N\)과 발사되는 화살의 횟수 \(Q\)가 공백을 사이에 두고 주어진다.
두 번째 줄에는 위치 \(i\) (\(1 ≤ i ≤ N\))에 놓을 수 있는 건초 더미의 방어력 \(D_1 , D_2 , \cdots, D_N\)이 공백을 사이에 두고 주어진다.
세 번째 줄부터 \(Q\)개의 줄에 걸쳐 \(Q\)개의 정수 쌍이 주어진다. 이 중 \(j\) (\(1 ≤ j ≤ Q\))번째줄에는 \(X_j\)와 \(P_j\)가 공백을 사이에 두고 주어진다.
\(Q\)개의 줄을 출력한다. 이 중 \(j\) (\(1 ≤ j ≤ Q\))번째 줄에는 \(f(X_j , P_j )\)의 값을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 6점 | \(N, Q ≤ 18\) |
2 | 16점 | \(N, Q ≤ 5\, 000\) |
3 | 18점 | \(1 ≤ i ≤ N\)인 모든 \(i\)에 대하여 \(D_i ≤ 300\) |
4 | 32점 | \(1 ≤ i < N\)인 모든 \(i\)에 대하여 \(D_i ≤ D_{i+1}\) |
5 | 28점 | \(N = Q\), \(1 ≤ j ≤ Q\)인 모든 \(j\)에 대하여 \(X_j = j\), \(P_1 = P_2 = \cdots = P_Q\) |
6 | 16점 | \(1 ≤ j ≤ Q\)인 모든 \(j\)에 대하여 \(X_j = N\) |
7 | 12점 | \(1 ≤ i < j ≤ N\)인 모든 \(i\), \(j\)에 대하여 \(D_i ≠ D_j\) |
8 | 22점 | 추가 제약 사항 없음. |
5 6
2 5 6 1 12
1 1
5 14
2 8
3 7
4 14
5 11
2
-1
2
4
15 5
3 6 1 1 10
1 10
2 10
3 10
4 10
5 10-1
-1
3
3
1riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 1차 대회 > 중등부 3번
평가 및 의견
건초 더미
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
건초 더미