레이팅 미적용소들은 재미있는 새 게임을 발명하기 위해 열심히 노력하고 있다. 현재 시도 중인 게임 하나는 \(N\)개의 구간의 집합을 사용한다(\(1\le N\le 2\cdot 10^5\)). \(i\)번째 구간은 수직선 위의 위치 \(a_i\)에서 시작해 위치 \(b_i \geq a_i\)에서 끝난다. \(a_i\)와 \(b_i\)는 모두 \(0 \ldots M\) 범위의 정수이며, \(1 \leq M \leq 5000\)이다.
게임을 하기 위해 베시는 어떤 구간(예를 들어 \(i\)번째 구간)을 선택하고, 사촌 엘시도 어떤 구간(예를 들어 \(j\)번째 구간, 베시의 구간과 같을 수도 있다)을 선택한다. 어떤 값 \(k\)가 주어졌을 때, \(a_i + a_j \leq k \leq b_i + b_j\)이면 둘이 이긴다.
\(0 \ldots 2M\) 범위의 모든 값 \(k\)에 대해, 베시와 엘시가 게임에서 이길 수 있는 순서쌍 \((i,j)\)의 개수를 세어라.
출제자: Benjamin Qi
배점
- 테스트 케이스 1-2는 \(N\le 100, M\le 100\)을 만족한다.
- 테스트 케이스 3-5는 \(N\le 5000\)을 만족한다.
- 테스트 케이스 6-20은 추가 제약이 없다.
출제자: Benjamin Qi
입력의 첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(N\)개의 줄에 각 구간을 나타내는 정수 \(a_i\)와 \(b_i\)가 주어진다.
\(0 \ldots 2M\) 범위의 각 값 \(k\)에 대해 한 줄씩, 총 \(2M+1\)개의 줄을 출력한다.
2 5
1 3
2 50
0
1
3
4
4
4
3
3
1
1In this example, for just \(k=3\), there are three ordered pairs that will allow
Bessie and Elie to win: \((1, 1)\), \((1, 2),\) and \((2, 1)\).
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Silver