Орон сууцнууд

2s

512MB

1009

0%

Sorting and Searching

$n$ өргөдөл гаргагч, $m$ сул орон сууц байна. Аль болох олон өргөдөл гаргагч орон сууц авахлаар орон сууцуудыг хуваарил.

Өргөдөл гаргагч бүр хүссэн орон сууцны хэмжээтэй бөгөөд үүнд хангалттай ойр хэмжээний орон сууцыг авна.

https://cses.fi/problemset/task/1084

Оролтын формат

Эхний мөрөнд гурван бүхэл тоо $n$ , $m$ , $k$ байна: өргөдөл гаргагчдын тоо, орон сууцны тоо, зөвшөөрөгдөх хамгийн их зөрүү.

Хоёр дахь мөрөнд $n$ бүхэл тоо $a_1, a_2, \ldots, a_n$ байна: өргөдөл гаргагч бүрийн хүссэн орон сууцны хэмжээ. Хүссэн хэмжээ нь $x$ бол өргөдөл гаргагч нь $x-k$ болон $x+k$ хоёрын хоорондох хэмжээтэй аль ч орон сууцыг авна.

Сүүлийн мөрөнд $m$ бүхэл тоо $b_1, b_2, \ldots, b_m$ байна: орон сууц бүрийн хэмжээ.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: орон сууц авах өргөдөл гаргагчдын тоо.

Хязгаарлалт

$1 \le n, m \le 2 \cdot 10^5$
$0 \le k \le 10^9$
$1 \le a_i, b_i \le 10^9$

Жишээ

Оролт1

4 3 5
60 45 80 60
30 60 75

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...