페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8263
서브태스크

소들의 사진 촬영 1초 1024MB

문제

Farmer John's 농장은 무성한 식물로 가득 차 있고, 모든 소들은 그들의 자연미를 담은 사진을 찍고 싶어한다. 하지만 Bessie는 다른 일정이 있어 방해하지 않으려 한다.

Bessie는 현재 XY 평면에서 (X, 0)에 서 있고, 목표는 (0, Y)로 가는 것이다. 여기서 1 \leq X, Y \leq 10^6이다. 하지만 N (1 ≤ N ≤ 3⋅10^5) 마리의 다른 소들이 X축에 위치하게 되었고, 소 i는 (x_i, 0) 위치에 있으며, 사진사는 (0, y_i) 위치에 있으며 사진을 찍을 준비가 되어 있다. 그들은 시간 s_i (1 ≤ s_i < T) 전에 사진을 찍기 시작하며, 오랜 시간 동안 계속 포즈를 취한다. 여기서 1 \leq T \leq N+1이다.

Bessie는 모든 소들의 사진 스케줄을 알고 있고, 가장 짧은 유클리드 거리를 따라 목표 지점에 도달하고자 한다. 단, 사진사를 포함한 소들의 시야를 교차하지 않도록 해야 한다. 즉, 그녀의 경로는 여러 개의 선분으로 이루어진다.

Bessie가 시간 t에 출발한다면, 시간 si \leq t인 모든 사진사/소 쌍의 시야를 피하게 되고, 최종 목표 지점까지의 거리는 d_t가 된다. 각 시간 t에 대해 \lfloor d_t \rfloor 값을 구하라.


입력

첫 번째 줄에는 N과 T가 주어진다. 각각 X축에 포즈를 취하는 소들의 수와 Bessie가 출발할 수 있는 시간 범위이다.

두 번째 줄에는 Bessie의 시작 X 좌표와 목표 Y 좌표 X와 Y가 주어진다.

그 다음 N개의 줄에는 s_i, x_i, y_i가 주어진다. 각 소의 사진 시작 시간, X축에서의 위치, 그리고 Y축에서의 사진사 위치이다.

  • 모든 x_i는 서로 다르고, X와도 다르다.

  • 모든 y_i는 서로 다르고, Y와도 다르다.

  • s_i는 오름차순으로 주어진다. (s_i \leq s_i+1)


출력

T개의 줄에 대해 각 시간 t에 대해 \lfloor d_t \rfloor 값을 출력한다.


부분문제

번호 점수 조건
#110점

N \le 100

#220점

N \le 3000

#330점

T \le 10

#440점

추가 제약 조건 없음


예제1

입력
45
67
175
244
316
429
출력
9
9
9
10
12

예제2

입력
23
107
1210
191
출력
12
16
16

t=0 -> ⌊\sqrt{149}⌋=12

t=1 -> ⌊14+\sqrt{5}⌋=16


예제3

입력
56
89
135
141
3107
492
566
출력
12
12
12
12
14
14

출처

USACO 2025 January Gold

역링크