빛의 파장 겹침
골드 III의견: 0
광학 연구소에는 \(N\)개의 광원이 있다. 광원 \(i\)는 정수 파장 구간 \([l_i, r_i]\)를 커버한다. 커버하는 파장 위치는 \(l_i, l_i+1, \dots, r_i\)의 각 정수이다.
\(Q\)개의 실험이 주어진다. 각 실험에서는 광원의 부분집합 \(S\)가 주어지며, \(S\)에 속한 광원들이 커버하는 파장 위치의 합집합 크기 (서로 다른 정수 파장 위치의 수)를 구하여야 한다.
- \(1 \le W \le 5\,000\)
- \(1 \le N \le 60\)
- \(1 \le Q \le 1\,000\)
- \(1 \le l_i \le r_i \le W\)
- 각 실험에서 광원은 최대 \(20\)개
첫째 줄에 파장 범위 상한 \(W\), 광원 수 \(N\), 실험 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 광원 \(i\)의 구간 \(l_i\), \(r_i\)가 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 실험 정보가 주어진다. 각 줄의 첫 번째 수는 사용할 광원의 수 \(k\)이고, 이어서 \(k\)개의 광원 번호 (\(1\)-인덱스)가 공백으로 구분되어 주어진다.
\(Q\)개의 줄에 걸쳐 각 실험에서 커버되는 파장 위치의 수를 순서대로 출력한다.
20 5 5
2 8
5 12
10 15
1 4
13 20
2 1 2
2 3 4
3 1 2 3
1 5
5 1 2 3 4 5
11
10
14
8
20
광원 \(1,2\)의 합집합은 \([2,12]\)로 \(11\)개. 광원 \(3,4\)의 합집합은 \([1,4] \cup [10,15]\)로 \(10\)개. 광원 \(1,2,3\)은 \([2,15]\)로 \(14\)개.
10 3 3
1 3
5 7
9 10
2 1 2
2 2 3
2 1 3
6
5
5
광원 \(1,2\): \([1,3]\cup[5,7]\)로 \(6\)개. 광원 \(2,3\): \([5,7]\cup[9,10]\)로 \(5\)개. 광원 \(1,3\): \([1,3]\cup[9,10]\)로 \(5\)개.
riseoj 작성
출처 Original
평가 및 의견
빛의 파장 겹침
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
빛의 파장 겹침