Informatica Online Judge

  비무장 지대 [1758 / 06DE]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 1   Total Tried : 1


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[2016 나는코더다 송년 대회 (wcipeg.com)]

Background

서기 12117년, 남한과 북한은 한반도의 위대한 지성인 최석환 (gs12117) 선생을 기리기 위해서 통일을 선언했다.

(1998년생 이원형과 아무 관계 없는) 대한민국의 이원형 장군은 조국의 사이버 국방을 책임지는 위대한 군인이다. 그는 지금 비무장 지대에 쌓여있는 지뢰를 어떻게 제거해야 하는지에 대해서 고민하고 있다. 비무장 지대는 0부터 $10^9$까지의 수직선으로 모델링할 수 있으며, 정확히 $N$($1 <= N <= 10^6$) 개의 지뢰가 묻혀 있으며, 이 중 $i$번째 지뢰는 $X_i$ ($0 <= X_i <= 10^9$)위치에 묻혀 있다. 지뢰가 묻혀있는 위치 $X_i$ 에서 이상이 감지된다면, 지뢰는 폭발한다.

핵지뢰부터 갤럭시 노트 7까지, 다양한 형태의 폭탄이 비무장 지대에 묻혀 있기 때문에, 이들의 폭발 양상은 다른 형태를 띈다. $i$번째 지뢰는 왼쪽으로 $L_i$, 오른쪽으로 $R_i$ 만큼의 범위로 폭발하며, 이는 $[X_i - L_i, X_i + R_i]$ 폐구간이 지뢰의 폭발 범위라는 것이다. ($1 <= L_i, R_i <= 10^9$) 지뢰의 폭발은 연속적인 지뢰의 폭발을 낳는다. 아직 폭발되지 않은 다른 지뢰의 중심이 폭발 범위 안에 들어간다면, 이 지뢰 역시 폭발하게 된다.

이원형 장군은 1개의 지뢰를 시범적으로 터트릴 예정이지만, 비무장 지대에는 다양한 문화 유산과 멸종위기 동물들이 살고 있다. 이원형 장군은 이를 최대한 보호하기 위해서, 사전 조사를 거치려고 한다. 이원형 장군은 $M$($1 <= M <= 300,000$) 개의 보호 구역 위치 $C_i$ ($0 <= C_i <= 10^9$)를 지정해 놓았으며, 각각의 보호 구역에 대해서, 해당 보호 구역을 파괴할 수 있는 지뢰의 개수를 구하고 싶어한다. 해당 보호 구역을 파괴할 수 있는 지뢰라는 것은, 해당 지뢰를 터트렸을 때, 연속적인 폭발 반응의 결과로 해당 보호 구역이 어떤 폭발한 지뢰의 폭발 범위 안에 들어갔음을 뜻한다.

젊은 시절 유능한 코이충으로 각광받던 이원형 장군이었지만, 지금은 대국민 담화를 준비해야 해서 너무나도 바쁘다. 여러분들이 이원형 장군을 대신해서 문제를 풀어주자.

Input

첫번째 줄에 지뢰의 수 $N$, 보호구역의 수 $M$이 주어진다. ($1 <= N <= 10^6$, $1 <= M <= 300,000$)

이후 $N$ 개의 줄이 주어진다. 이 중 $i$번째 줄에는, $i$번 지뢰의 위치, 폭발 범위를 나타내는 세 정수 $X_i, L_i, R_i$가 순서대로 주어진다. ($0 <= X_i <= 10^9$, $1 <= L_i, R_i <= 10^9$)

이후 $M$ 개의 줄이 주어진다. 이 중 $i$번째 줄에는, 보호 구역의 위치인 정수 $C_i$ 가 주어진다. ($0 <= C_i <= 10^9$)

Output

$M$ 개의 줄에 걸쳐 각각의 보호 구역을 파괴할 수 있는 지뢰의 수를 하나의 정수로 출력한다.

IO Example

입력
4 4
10 5 12
4 5 6
15 1 1
20 10 80
101
100
0
14

출력
0
3
1
4

예제 설명
101에 있는 보호 구역을 터트릴 수 있는 폭탄은 없다.
100에 있는 보호 구역은 4번 지뢰가 터지면 파괴된다. 1, 2, 4번 지뢰를 처음에 터트리면, 4번 지뢰가 최종적으로 폭발한다.
0에 있는 보호 구역은 2번 지뢰가 터지면 파괴된다. 처음에 2번 지뢰를 터트려야만 2번 지뢰가 터진다.
14에 있는 보호 구역은 1, 3, 4번 지뢰가 터지면 파괴된다. 1, 2, 3, 4번 지뢰를 처음에 터뜨리면, 이 중 한 지뢰가 터진다. 즉 지뢰를 어떻게 터트려도 이 보호 구역은 파괴된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]