| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 160 | 77 | 65 | 53.279% |
당신은 구간 보관 서비스를 운영하고 있다. 현재 보관소에는 총 $N$개의 구간이 보관되어 있고, 이 중 $i$번째 구간은 수직선에서 $[l_i, r_i]$로 나타난다.
보관소에 총 $Q$회의 레이저 폭격이 예고되었다! 이 중 $j$번째 레이저 빔의 피해 범위는 구간 $[s_j, e_j]$로 나타낼 수 있다. 당신은 각 레이저 빔이 날아올 때마다, 보관된 구간을 적절히 옮겨서 빔에 맞는 구간이 없도록 해야 한다.
구체적으로, 보관된 각 구간 $[l_i, r_i]$에 대해 적절한 정수 $x_{ij}$를 정한다. 이 때 모든 $(i, j)$에 대해 $[l_i+x_{ij}, r_i+x_{ij}]$와 $[s_j, e_j]$가 겹치는 부분의 길이가 0ドル$이 되도록 해야 한다. 두 구간 $[a, b]$와 $[c, d]$가 겹치는 부분의 길이는 $\max(0, \min(b, d) - \max(a, c))$이다.
구간은 무겁기 때문에 기계를 사용하여 옮기는데, 한 번 옮길 때마다 (이동 거리) $\times$ (구간 길이) 만큼의 전기료가 나온다. 즉, $j$번 레이저 빔이 오기 전에 사용하는 전기료는 $\sum_{i=1}^{N} (r_i-l_i)|x_{ij}|$이다.
각 레이저 빔이 지나간 후에 당신은 옮겼던 모든 구간을 다시 원래 위치로 되돌려 놓는다. 옮길 때와 돌려놓을 때 모두 똑같이 비용이 발생함을 유의하라.
당신은 각 레이저 빔마다 최소한의 전기료를 사용하여 모든 구간을 안전하게 관리하려고 한다. 이때의 비용을 계산하여 보자.
첫째 줄에 구간의 개수 $N$과 예고된 레이저 폭격의 수 $Q$가 주어진다. (1ドル \le N, Q \le 250,000円$)
이후 $N$개의 줄에 걸쳐, 그 중 $i$번째 줄에는 $i$번째 보관된 구간의 양 끝점 $l_i$와 $r_i$가 주어진다. (1ドル \le l_i < r_i \le 1,000円,000円$)
이후 $Q$개의 줄에 걸쳐, 그 중 $j$번째 줄에는 $j$번째 레이저 빔 피해 범위의 양 끝점 $s_j$와 $e_j$가 주어진다. (1ドル \le s_j < e_j \le 1,000円,000円$)
입력으로 들어오는 모든 수는 정수이다.
각 레이저 빔에 대해, 현재 상태에서 모든 구간을 안전한 위치로 옮겼다가 돌려놓기 위해 필요한 최소 전기료를 $Q$개의 줄에 순서대로 출력한다.
2 2 1 5 4 8 3 5 8 9
24 0
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2025 예선 C번