고기 파티
플래티넘 II의견: 0
오늘은 고기 파티가 열리는 날이다. 파티에 걸맞도록, 기다란 그릴 위에 잘 구워진 고기가 총 \(N\)개 놓여 있다.
그릴을 \(10^9\) 의 길이를 가진 선분이라고 하고, 그릴의 왼쪽 끝을 좌표 \(0\), 오른쪽 끝을 좌표 \(10^9\) 이라고 하자. 각 고기는 그릴 위에서 특정 구간을 차지하고 있으며, 양의 정수로 표현되는 맛 수치를 각각 가진다. \(i\)번째 고기는 (\(1 \le i \le N\)) 구간 \([s_i, e_i]\)에 해당하는 좌표를 차지하고 있으며 맛 수치는 \(t_i\)이다. 여러 고기가 겹쳐 있을 수 있다.
파티에는 \(M\) 명의 사람이 참석하였다. \(1\) 번 사람부터 \(M\) 번 사람까지 번호 순서대로 그릴 앞에 서서 각자 먹을 고기를 가져간다. 고기를 가져가는 방법은 다음과 같다.
- \(j\) 번 사람은 (\(1 \le j \le M\)) 긴 꼬치 두 개를 가지고 와서 각각 \(a_j + 0.1\), \(b_j + 0.9\) 좌표에 찔러 넣는다. (\(a_j \le b_j\)) 좌표 \(x\)에 찔러 넣은 꼬치는 \(s_i \le x \le e_i\)를 만족하는 모든 고기에 꽂히게 된다.
- 그다음, 꼬치를 통째로 들고 자리로 돌아간다. 이때 하나 이상의 꼬치가 꽂힌 고기는 모두 같이 들려 가고, 그릴 위에서 사라진다.
- 둘 중 하나의 꼬치만 꽂힌 고기는 들고 가다 바닥에 떨어진다. 두 꼬치가 모두 꽂힌 고기만 자리로 가져가서 먹을 수 있다.
파티의 주최자인 당신은 각 사람이 어떤 고기를 가져가서 먹게 될지가 궁금하다. 각 사람이 가져가서 먹게 되는 고기의 맛 수치의 합을 구하여 보자. 들고 가다 떨어트린 고기는 합에서 제외해야 함에 유의하라.
- 주어지는 모든 수는 정수이다.
- \(1 \le N, M \le 250\,000\)
- \(0 \le s_i < e_i \le 10^9\) (\(1 \le i \le N\))
- \(1 \le t_i \le 10^9\) (\(1 \le i \le N\))
- \(0 \le a_j \le b_j \le 10^9 - 1\) (\(1 \le j \le M\))
첫 번째 줄에 고기의 수 \(N\)과 사람의 수 \(M\)이 주어진다.
다음 줄부터 \(N\)개의 줄에 걸쳐, 이 중 \(i\)번째 줄에는 \(i\)번째 고기가 차지하는 구간과 맛 수치를 나타내는 세 정수 \(s_i\), \(e_i\), \(t_i\)가 주어진다.
다음 줄부터 \(M\)개의 줄에 걸쳐, 이 중 \(j\)번째 줄에는 \(j\) 번 사람이 꼬치를 어느 좌표에 찔러 넣을지를 나타내는 두 정수 \(a_j\), \(b_j\)가 주어진다.
\(M\)개의 줄에 걸쳐, 이 중 \(j\)번째 줄에는 \(j\) 번 사람이 가져가서 먹게 되는 고기의 맛 수치의 합을 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 5점 | \(N, M \le 1\,000\). |
2 | 9점 | \(e_i - s_i \le 5\) (\(1 \le i \le N\)). |
3 | 11점 | \(s_i < s_{i+1}\), \(e_i > e_{i+1}\) (\(1 \le i \le N - 1\)). |
4 | 23점 | \(e_i - s_i = e_1 - s_1\) (\(2 \le i \le N\)). |
5 | 52점 | 추가 제약 조건이 없음. |
5 3
2 7 3
5 6 9
3 5 2
1 3 6
4 8 7
3 6
2 4
5 5
3
0
9
6 3
1 12 1
2 11 10
3 10 100
4 9 1000
5 8 10000
6 7 100000
1 11
5 9
6 8
1
110
0
5 2
1 5 5
2 6 2
4 8 3
5 9 4
7 11 6
4 5
8 10
5
6
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2023 > 2차 대회 > 초등부 4번 / 중등부 3번
평가 및 의견
고기 파티
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
고기 파티