Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
D. Өргөн чөлөөнд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Намрын налгар орой өргөн чөлөөгөөр алхах шиг сайхан юм хаа байна. $n$ ширхэг хүн яг ингэж шийдээд алхав аа. Тус өргөн чөлөөг $Ox$-ээр төлөөлүүлье. Алхаж буй хүн тус бүрийн хувьд $t_i$, $si$, $fi$ гэсэн 3 хувьсагчаар төлвийг нь тодорхойлж болно. Энд: $i$-дэх хүний алхаж эхлэх үеийн хугацаа, эхэлсэн болон дууссан цэгүүд харгалзан $ti$, $si$, $fi$ байна.
Хүн бүр $si$-ээс $fi$ хүртэлх зайг $1$; $-1$ хурдтайгаар (чиглэлээс хамаарч), шулуун явж туулна.
$i$-дэх хүн гарч ирмэгц $si$ дэх нь $fi$ рүү явах нөхцөлтэй. Хэрэв 2 болон түүнээс их хүн чиглэлээс үл хамааран нэг цаг мөч, нэг цэгт уулзвал хүн бүр хоорондоо гар барих ёстой.
Хүн тус бүрийн хувьд алхаж байх хугацаандаа нийт хэдэн удаа бусадтайгаа гар барихыг тооц.
Жич: $i$- дэх хүн $si$ болон $fi$ дээрх бусад хүмүүстэй гар барьж болох боловч өргөн чөлөөнд орж ирэхээс өмнө гар барьж болохгүй. Мөн $fi$ цэгт хүрсэн хүн өргөн чөлөөнөөс гарах ёстой ба бусад хүмүүстэй гар барихгүй гэж үз.
Оролт
Эхний мөрөнд $n$ $(2 ≤ n ≤ 1000)$ буюу нийт алхах хүний тоо байна.
$n$ ширхэг мөрөнд $n$ хүн агуулагдана. $i$-р мөрөнд $ti$, $si$, $fi$ $(1 ≤ ti, si, fi ≤ 10^6, si ≠ fi)$ гэсэн гурван эерэг бүхэл тоо байна.
Гаралт
Гаралтын нэг мөрөнд $n$ бүхэл тоон $r1$, $r2$, ... , $rn$ дараалал байна. ($ri$ нь $i$-дэх хүн өргөн чөлөөгөөр алхахдаа нийт хэдэн хүнэтэй гар барьсаныг илтгэнэ)
Орчуулсан: ERDENI
Жишээ тэстүүд
Оролт
3 1 1 10 5 8 2 9 9 10
Гаралт
2 1 1
Оролт
3 3 2 4 4 3 4 3 6 4
Гаралт
2 2 2