Codeforces Round #716 (Div. 2)
04:52:43 |
Codeforces Round #717 (Div. 2)
2 өдрийн дараа |
Codeforces Round #718 (Div. 1)
4 өдрийн дараа |
Codeforces Round #718 (Div. 2)
4 өдрийн дараа |
Codeforces Global Round 14
13 өдрийн дараа |
D. Хамгийн урт дэд дараалал
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд $n$ элементтэй $a$ массив болон $m$ тоо өгөгдөнө. $a$ массиваас дэд дараалал үүсгэж уг дэд дарааллын гишүүдийн ХБЕХ-г ол. Энэ ХБЕХ-г $l$-р тэмдэглэвэл $l ≤ m$ байх $a$ массиваас үүсч болох дэд дарааллуудаас хамгийн урт дэд дарааллыг ол.
Дэд дараалал нь $a$ массивын зарим элементийг устгах замаар үүсгэсэн массив байна. Бүх элементийг устгаж болох ба нэг ч элемент устгахгүй байж бас болно.
Хоосон массивын хувьд ХБЕХ нь $1$ байна.
Оролт
Эхний мөрөнд хоёр ширхэг бүхэл тоон утга $n$ ба $m$ байх ба харгалзан $a$ массивын хэмжээ болон бодлогын нөхцөл болох тоо юм. $(1 ≤ n, m ≤ 10^6)$
Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $a_{i}$ байх ба эдгээр нь $a$ массивын элементүүд юм. $(1 ≤ a_{i} ≤ 10^9)$
Гаралт
Эхний мөрөнд хоёр бүхэл тоон утга $l$ ба $k_{max}$ байх ба харгалзан ХБЕХ-н утга болон хамгийн тохиромжтой дэд дарааллын элементийн тоо юм. ($1 ≤ l ≤ m, 0 ≤ k_{max} ≤ n$)
Хоёр дахь мөрөнд $k_{max}$ ширхэг бүхэл тоон утга байх ба дэд дарааллын элементүүдийн $a$ массив дахь байрлалыг өсөхөөр эрэмбэлэн хэвлэнэ.
Та байж болох хамгийн их урттай дэд дарааллуудаас алийг нь ч хэвлэсэн болно.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
7 8 6 2 9 2 7 2 3
Гаралт
6 5 1 2 4 6 7
Оролт
6 4 2 2 2 3 3 3
Гаралт
2 3 1 2 3