레이팅 미적용\(N\)명의 참가자가 대회에 참가했고, 각자 \(1\)부터 \(N\)까지 서로 다른 순위를 기록했다. 결승 라운드에 참가자를 초대하는 데 사용되는 기준이 \(C\)개 있으며, \(i\)위 참가자는 그중 지정된 \(n_i\)개 (\(1\le n_i\le C\))를 만족한다.
초대 과정은 다음과 같이 진행된다. 먼저, \(1\)번 기준을 만족하는 상위 \(f_1\)명이 초대된다. 그런 다음, 아직 초대되지 않은 학생들 중 \(2\)번 기준을 만족하는 상위 \(f_2\)명 (남은 인원이 \(f_2\)명보다 적으면 남은 전원)이 초대된다. 이 과정은 각 \(i\)에 대해 \(1\)부터 \(C\)까지 반복된다 (\(1\le f_i\le N\)).
하지만 일부 참가자는 결승 라운드 참가를 거절하며, 이 경우 초대 대상을 정할 때 그들은 무시된다.
\(1\dots N\)의 순열 \(p_1, p_2, \dots, p_N\)이 주어진다. 각 \(i\) (\(0\)부터 \(N-1\)까지)에 대해, \(p\)의 처음 \(i\)개 원소가 나타내는 순위의 참가자들이 참가를 거절했을 때 초대되는 참가자들의 순위의 합을 구하라.
Problem credits: Benjamin Qi
SCORING
- 입력 4-6: \(N, C \le 10^3, \sum n_i \le 10^4\)
- 입력 7-8: \(C=1\)
- 입력 9-10: \(C=2\)
- 입력 11-16: 추가 제약 없음.
Problem credits: Benjamin Qi
첫째 줄에 \(N\)과 \(C\) (\(1\le N,C\le 10^5\))가 주어진다.
다음 줄에 \(f_1,f_2, \dots, f_C\)가 주어진다.
다음 줄에 \(p_1, \dots, p_N\)이 주어진다.
다음 \(N\)개의 줄에 각각 \(n_i\) (\(1\le n_i\le C\))와 그 뒤로 \([1, C]\) 범위의 서로 다른 정수 \(n_i\)개가 주어지며, 이는 \(i\)위 참가자가 만족하는 기준들을 나타낸다. \(\sum n_i\le 10^6\)임이 보장된다.
\(N\)개의 줄에 걸쳐, 각 거절이 일어나기 전 초대 대상자들의 순위의 합을 출력한다.
5 1
3
5 1 3 2 4
1 1
1 1
1 1
1 1
1 16
6
9
6
4There is only one criterion. The top three remaining contestants who have not
declined will be invited.
5 4
1 1 1 1
1 2 3 4 5
1 1
2 1 2
2 2 3
2 3 4
1 410
14
12
9
5Initially, the \(i\)th contestant gets invited under criterion \(i\) for all
\(1\le i\le 4\).
After the first declination, the \(i+1\)th contestant gets invited under criterion
\(i\) for all \(1\le i\le 4\).
6 10
5 6 4 1 3 3 3 6 5 3
1 4 6 5 2 3
1 9
5 4 3 9 5 10
10 6 2 10 1 7 8 3 9 4 5
10 4 5 3 1 2 9 10 6 7 8
2 3 1
8 1 9 7 4 3 10 6 221
20
16
10
5
3riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Silver