소들은 재미있는 새로운 게임을 만들려고 노력하고 있습니다. 그들의 현재 작업 중 하나는 일련의 N 간격(1≤N≤2⋅10⁵)에 관한 것입니다. 여기서 i번째 간격은 숫자 라인의 위치 ai에서 시작하여 위치 bi≥ai에서 끝납니다. ai 및 bi는 0…M 범위의 정수이며, 여기서 1≤M≤5000입니다.

게임이 작동하는 방식은 Bessie가 간격(i번째 간격이라고 하자)을 선택하고 그녀의 사촌 Elsie가 간격을 선택하는 것입니다(j번째 간격이라고 하자. Bessie가 선택한 것과 동일한 간격일 수 있음). 어떤 값 k가 주어지면 ai+aj≤k≤bi+bj이면 승리합니다.

0…2M 범위의 각 k 값에 대해 Bessie와 Elsie가 게임에서 승리할 수 있도록 하는 순서쌍(i,j)의 수를 계산합니다.

#5356 upload 2 done 2 how_to_reg 2

복잡한 간격 (Convoluted Intervals) timer 1s memory 256MB

#5356

복잡한 간격 (Convoluted Intervals) 1s 256MB