Codeforces Round #793 (Div. 2)
23:41:34 |
Educational Codeforces Round 129 (Rated for Div. 2)
23:41:34 |
Codeforces Round #794 (Div. 1)
4 өдрийн дараа |
Codeforces Round #794 (Div. 2)
4 өдрийн дараа |
D. Сэлгэмэлийн солилцоо
хугацааны хязгаарлалт 5 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд $1, 2, ..., n$ тоонуудаас бүрдсэн $p$ сэлгэмэл болон $(a_{j}, b_{j})$ байрлалыг илтгэх $(a_{j}, b_{j})$ хосууд өгөгджээ.
Алхам болгондоо та өгөгдсөн байрлалуудаас нэг хосыг сонгон тоонуудыг нь солиж болно. Таны гаргаж ирж чадах толь зүйн хамгийн их сэлгэмэл юу вэ?
$p$ болон $q$-г $1, 2, ..., n$ тоонуудын 2 сэлгэмэл гэж үзье. Хэрвээ $1 ≤ i ≤ n$ тоо оршин байгаа бөгөөд $1 ≤ k < i$-ийн хувьд $p_{k} = q_{k}$ харин $i$-ийн хувьд $p_{i} < q_{i}$ байвал $p$ нь толь зүйн хувьд $q$-ээс жижигхэн юм.
Оролт
Эхний мөрөнд $p$ сэлгэмэлийн урт болон байрлалуудын хосуудын дугаар болох $n$ ба $m$ ($1 ≤ n, m ≤ 10^{6}$) 2 бүхэл тоо өгөгдөнө.
2 дахь мөрөнд $n$ ширхэг ялгаатай бүхэл тоонууд $p_{i}$ ($1 ≤ p_{i} ≤ n$) өгөгдөнө. Эдгээр нь $p$ сэлгэмэлийн элемэнтүүд юм.
Сүүлийн $m$ ширхэг мөр болгон $(a_{j}, b_{j})$ ($1 ≤ a_{j}, b_{j} ≤ n$) гэсэн 2 бүхэл тоо агуулна. Эдгээр нь солих байрлалууд юм. Энд танд солих байрлалуудыг өгсөн, харин утгыг нь биш гэдгийг анхаарна уу.
Гаралт
Ганцхан мөрөнд $n$ ширхэг ялгаатай бүхэл тоонуудыг $p'_{i}$ ($1 ≤ p'_{i} ≤ n$) хэвлэнэ үү. Энэ нь таны гаргаж чадах толь зүйн хамгийн их сэлгэмэл байх ёстой.
Орчуулсан: Энхлут
Жишээ тэстүүд
Оролт
9 6 1 2 3 4 5 6 7 8 9 1 4 4 7 2 5 5 8 3 6 6 9
Гаралт
7 8 9 4 5 6 1 2 3