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 값을 구하라.

#8263 upload - done - how_to_reg - call_split Subtask

소들의 사진 촬영 timer 1s memory 1024MB

#8263
Subtask

소들의 사진 촬영 1s 1024MB