기차 지연

시간 제한3초메모리 제한1024 MB

요약
여러 기차에 지연 구간이 주어질 때, 각 질의 시각마다 빨간색으로 표시되는 행의 극대 연속 구간 개수를 구한다.
난이도

어려움10점 중 9점

유형
세그먼트 트리, 정렬, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

IOI 도시는 세계에서 가장 인구가 많고 바쁜 도시이다. 일반적으로 하루는 86 40086 \ 400초이지만, IOI 도시에서는 시간의 단위 '쵸'를 정의하여 하루를 무려 101210^{12}쵸로 세분화하여 사용한다. 하루의 시작을 00쵸로 정의하고, 실수 t(0≤t<1012)t(0 \leq t < 10^{12})에 대하여 00쵸에서 tt쵸가 지난 뒤의 시각을 tt쵸로 정의한다. 1012−110^{12}-1쵸에서 11쵸가 지나면 다음날 00쵸가 된다.

IOI 도시는 교통량이 어마어마하기 때문에, IOI 도시의 기차역에서는 매일 101210^{12} 개의 기차가 출발한다. 101210^{12}개의 기차는 00부터 1012−110^{12} - 1 까지의 정수 번호가 붙어 있으며, i(0≤i≤1012−1)i (0 \leq i \leq 10^{12} - 1)번 기차는 ii쵸에 출발하기로 예정되어 있다.

IOI 도시의 기차역에서는 많은 기차의 탑승 정보를 표시하기 위해 101210^{12}개의 행이 있는 거대한 전광판을 가지고 있다. 전광판의 101210^{12}개의 행에는 00부터 1012−110^{12}-1까지의 번호가 붙어 있다. 그날 출발하기로 예정되어 있던 기차 중 아직 출발하지 않은 기차가 MM개라고 할 때, 전광판의 00번 행부터 M−1M-1번 행까지는 이 MM개의 기차의 정보를 번호가 커지는 순서대로 보여준다. 또한, 기차가 출발하기까지 KK쵸 이하로 남은 경우에는 탑승을 준비하라는 의미에서 해당 기차의 정보는 빨간색으로 표시하고, KK쵸 초과로 남은 경우에는 흰색으로 표시한다. 예를 들어, K=20K=20이고 모든 기차가 예정된 시각에 출발하는 경우, 5.55.5쵸에 전광판의 i(0≤i≤999 999 999 993)i(0 \leq i \leq 999 \ 999\ 999\ 993)번 행에는 i+6i+6번 기차의 정보가 표시된다. 또, 00번 행부터 1919번 행까지는 출발 시각이 25.525.5쵸 이전인 기차의 정보를 표시하고 있으므로 빨간색이며, 2020번 행부터 999 999 999 993999 \ 999\ 999\ 993번 행까지는 흰색이다.

아직 출발하지 않은 기차의 수 MM과 두 정수 l,r(0≤l≤r≤M−1)l, r(0 \leq l \leq r \leq M-1)에 대하여 다음 세 조건이 모두 성립할 경우, ll과 rr의 순서쌍 (l,r)(l, r)을 빨간색 연속 구간이라고 부른다.

  • 임의의 정수 k(l≤k≤r)k(l \leq k \leq r)에 대하여, 전광판의 kk번 행에서는 빨간색으로 정보를 표시하고 있다.
  • l=0l = 0이거나, 전광판의 l−1l-1번 행에서는 흰색으로 정보를 표시하고 있다.
  • r=M−1r = M-1 이거나, 전광판의 r+1r+1번 행에서는 흰색으로 정보를 표시하고 있다.

M≥1M\ge 1이고 모든 기차가 예정된 시각에 출발하는 경우, 전광판의 첫 몇 개의 행은 빨간색이고 나머지는 흰색이므로 빨간색 연속 구간의 개수는 11이다. 하지만 몇몇 기차가 지연될 경우, 기차의 번호 순서와 출발 시각 순서가 일치하지 않아 빨간색 연속 구간의 개수가 많아질 수 있다. 예를 들어, K=20K=20이고 33번 기차가 3030쵸 지연되어 3333쵸에 출발하고, 1010번 기차가 2020쵸 지연되어 3030쵸에 출발하는 경우, 5.55.5쵸에 M=999 999 999 995M = 999 \ 999 \ 999 \ 995이고 전광판에 표시되는 정보는 다음과 같다.

전광판의 행 번호00\[1,4]\[1,4]55\[6,20]\[6,20]\[21,999 999 999 994]\[21, 999\ 999 \ 999\ 994]
표시하고 있는 기차의 번호33\[6,9]\[6,9]1010\[11,25]\[11,25]\[26,999 999 999 999]\[26, 999\ 999\ 999\ 999]
색깔흰색빨간색흰색빨간색흰색

따라서 이 경우 빨간색 연속 구간은 (1,4)(1, 4)와 (6,20)(6, 20)이며 그 개수는 22이다.

빨간색 연속 구간의 개수가 많으면, 중요한 정보가 한곳에 모여 있지 않아 기차를 타는 사람들에게 혼란을 줄 수 있다. 따라서 기차가 지연될 경우, 각 순간에 빨간색 연속 구간의 개수를 파악한 후에, 이에 맞추어 전광판의 표시 형식을 바꾸거나 공지하는 등의 조치를 취해야 한다. 다행히도 20242024년까지는 많은 기차가 한꺼번에 지연된 사례가 없어서, 컴퓨터의 도움 없이 사람이 직접 빨간색 연속 구간의 개수를 파악하여 조치를 취했다.

그러나 20242024년 1212월 3131일 999 965 277 778999 \ 965 \ 277 \ 778쵸, 20252025년 11월 11일 출발 예정인 많은 기차가 지연되었다는 제보 NN개가 동시에 들어왔다. i(1≤i≤N)i(1 \leq i \leq N)번 제보에 의하면, 번호가 L_iL\_i 이상 R_iR\_i 이하인 기차의 출발 시각은 각각 D_iD\_i쵸만큼 늦추어졌다. 이때, 한 기차에 대해 출발 시각이 늦추어졌다는 제보가 여러 개인 경우, 이 기차의 출발 시각은 제보들에 대한 D_iD\_i의 합만큼 늦추어졌다고 한다. 당황한 IOI 기차역의 관리자는 20252025년 11월 11일 00쵸가 되기 전에 20252025년 11월 11일의 여러 시각에 대해 빨간색 연속 구간의 수를 파악해야 해서 여러분에게 도움을 요청했다. QQ개의 시각 T_1,T_2,…,T_QT\_1, T\_2, …, T\_Q가 주어졌을 때, 각 i(1≤i≤Q)i(1 \leq i \leq Q)에 대해 20252025년 11월 11일 T_i+0.5T\_i + 0.5쵸에 빨간색 연속 구간의 수를 구하여라.

입력

첫째 줄에 제보의 수 NN, 빨간색으로 표시하는지 여부의 기준이 되는 시간 KK가 공백을 사이에 두고 주어진다.

각 i(1≤i≤N)i (1 \leq i \leq N)에 대하여, i+1i+1번째 줄에는 ii번 제보의 내용 L_i,R_i,D_iL\_i, R\_i, D\_i가 순서대로 공백을 사이에 두고 주어진다.

N+2N+2번째 줄에, 빨간색 연속 구간의 수를 구해야 하는 시각의 수 QQ가 주어진다.

각 i(1≤i≤Q)i(1 \leq i \leq Q)에 대하여, i+N+2i+N+2번째 줄에는 T_iT\_i가 주어진다.

출력

QQ개의 줄에 걸쳐 정답을 출력한다. i(1≤i≤Q)i(1 \leq i \leq Q)번째 줄에는 20252025년 11월 11일 T_i+0.5T\_i + 0.5쵸에 빨간색 연속 구간의 수를 출력한다.

제한

  • 1≤N≤200 0001 \leq N \leq 200\ 000
  • 1≤K≤1012−11 \leq K \leq 10^{12} - 1
  • 각 1≤i≤N1 \leq i \leq N에 대하여, 0≤L_i≤R_i≤1012−10 \leq L\_i \leq R\_i \leq 10^{12}-1이고 1≤D_i≤1061 ≤ D\_i ≤ 10^6
  • 1≤Q≤200 0001 \leq Q \leq 200\ 000
  • 0≤T_1<T_2<…<T_Q≤1012−10 \leq T\_1 < T\_2 < … < T\_Q\leq 10^{12} - 1
  • 주어지는 모든 수는 정수이다.

예제2

  1. 예제 1

    입력
    4 20
3 3 30
10 10 20
999999999000 999999999999 1019
999999999000 999999999000 2
3
5
10
999999999999
    예상 출력
    2
1
0

  2. 예제 2

    입력
    4 10
1 4 3
8 10 10
18 19 1
18 20 1
5
0
1
6
7
21
    예상 출력
    1
2
2
1
1