Знаєте цю задачу?#13112

Знаєте цю задачу? (Розбір)

Назвемо неспадну підпослідовність , а незростаючу — , і оброблятимемо елементи зліва направо. Чи вдасться розподілити решту масиву, залежить лише від останнього елемента та останнього елемента . Новий елемент може приєднатися до , якщо він не менший за останній елемент , і до , якщо він не більший за останній елемент . Тож менший останній елемент і більший останній елемент ніколи не гірші. Порожня поводиться як , а порожня — як .

Досить двох чисел. Після обробки h_i один із двох останніх елементів — це саме h_i. Тому зберігаємо лише

Спочатку u = +\infty, d = -\infty. Нехай p = h_i, x = h_{i+1}.

Новий — максимум його кандидатів, новий — мінімум його кандидатів («неможливо», якщо кандидатів немає). Відповідь YES тоді й лише тоді, коли наприкінці або можливе. Це часу, і масив навіть не треба зберігати.

Усі порівняння нестрогі, бо однакові значення дозволені в обох підпослідовностях: розв'язок для строго монотонних підпослідовностей не проходить. Тримайте «неможливо» окремо від «порожня» і від справжніх значень: 10^9 — допустиме значення, тож воно не може правити за .

Зауваження: як знайти розбиття. Для кожного запам'ятовуємо, який перехід дав і , і йдемо назад від i = n. Рівносильний жадібний алгоритм: якщо h_i підходить лише одній підпослідовності, віддаємо його їй; якщо обом, дивимося на наступне значення w \ne h_i і віддаємо h_i до , якщо w < h_i, і до інакше. Дивитися лише на h_{i+1} недостатньо, бо перед може стояти довга серія однакових значень.