레이팅 미적용농부 존은 \(N\)마리의 소 (\(2 \leq N \leq 5\cdot 10^6\))를 기르고 있으며, 소들의 게으름을 이용해 길이 \(N\)의 음이 아닌 정수 배열 \(A\)를 정렬하게 하려고 한다. 그는 무거운 상자를 많이 가지고 있어서, 소 \(i+1\)이 소 \(i\)의 뒤에 오도록 소들을 한 줄로 세운 뒤, 소 \(i\)에게 상자 \(a_i\)개 (\(0\le a_i\))를 준다.
소들은 천성적으로 게을러서 항상 자신의 일을 남에게 떠넘기려 한다. 소 \(1\)부터 \(N-1\)까지 순서대로, 각 소는 자기 뒤의 소를 살펴본다. 소 \(i\)가 소 \(i+1\)보다 엄격히 많은 상자를 가지고 있다면, 소 \(i\)는 이것이 "불공평"하다고 생각하여 자신의 상자 하나를 소 \(i+1\)에게 준다. 이 과정은 모든 소가 만족할 때까지 반복된다.
그 후 농부 존은 각 소 \(i\)가 들고 있는 상자의 개수 \(b_i\)를 기록하여 이 값들로 배열 \(B\)를 만든다. \(B = sorted(A)\)이면 농부 존은 행복해진다. 불행히도, 농부 존은 \(A\)의 값 중 \(Q\)개 (\(2 \leq Q \leq \min(N, 100)\))를 제외하고 모두 잊어버렸다. 다행히도, 그 값들에는 첫 번째 소와 마지막 소에게 주려던 상자의 개수가 포함되어 있다. 농부 존이 기억하는 각 값은 \(a_{c_i}=v_i\) (\(1 \leq c_i \leq N\), \(1\le v_i\le 10^9\))를 나타내는 \(c_i \; v_i\)의 형태로 주어진다. 농부 존이 행복해지도록 빠진 값들을 채워 넣는 서로 다른 방법의 수를 \(10^9+7\)로 나눈 나머지를 구하라.
Problem credits: Suhas Nagar
SCORING
- 입력 3-4: \(N,v_i\le 100\)
- 입력 5-6: \(N\le 100\)이고 \(v_i \leq 10^6\)
- 입력 7-9: \(N \leq 2\cdot 10^5\)이고 \(v_i \le 10^6\)
- 입력 10-12: \(N \leq 2\cdot 10^5\)
- 입력 13-15: 추가 제약 없음.
Problem credits: Suhas Nagar
첫째 줄에 공백으로 구분된 두 정수 \(N\)과 \(Q\)가 주어지며, 각각 소의 수와 쿼리의 수를 나타낸다.
다음 \(Q\)개의 줄에 공백으로 구분된 두 정수 \(c_i \; v_i\)가 주어지며, 이는 소 \(c_i\)가 처음에 상자 \(v_i\)개를 들고 있음을 나타낸다. \(c_1 = 1\), \(c_Q = N\), \(c_i < c_{i+1}\) (소의 순서가 순증가)임이 보장된다.
소들이 게으른 정렬을 수행한 후 농부 존이 행복해지도록 값 \(a_i\)를 배정하는 서로 다른 방법의 수를 \(10^9+7\)로 나눈 나머지를 출력한다. 유효한 배정이 적어도 하나 존재함이 보장된다.
3 2
1 3
3 22In this example, FJ remembers the values at the ends of the array. The arrays
\([3,2,2]\) and \([3,3,2]\) are the valid arrays that will make FJ happy at the end
of the lazy sorting.
6 3
1 1
3 3
6 589riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > US Open > Platinum