Задача от алгоритмичен вид

Здравейте, трябва ми помощ със следната задача:

Успях да я направя, но ми минават само малък процент от тестовете, като останалите тайм-аутват(вероятно заради големия вход). В последствие разбрах, че оптималното решение на задачата се постига, чрез графи, обаче нищичко не ми хрумва, моля за помощ и насоки. Благодаря.

Щом е с графи защо не използваш GraphQL ?

Трябва ми решение на C++.

Не си преписал правилно задачата, в примерните данни, казваш, че имаш 15 заявки, но в примерния изход имаш само 7 отговора. Другите 8 къде са ? И какбо е това "i" в условието ? Как се разбира дали правим заявка от тип 1 или тип 2 ? Нещо не си преписал както трябва и задачата ти няма смисъл

1 i е заявка тип 1, 2 i е заявка тип 2. В примерния изход, който си посочил, редовете са 7, защото заявките от тип 1 са 7(а на output format-а пише, че трябва да вадим изход само за заявки от тип 1. Също така заявката се разбира каква е от pair-ите които подавам след стринга, например:
на втория ред на входа, който си посочил ти: 2 7 - заявка тип 2.
на третия ред на входа, който си посочил ти: 1 12 - заявка тип 1.
Също така, втория член на всяка двойка е цифра отговаряща на index в стринга

Мисля, че това са нещата, за които ме попита, пиши ако нещо съм пропуснал, но в условието на задачата няма грешка.

Това мнение е било редактирано от radbot на 30-05-2023, 11:15

> Препоръчителна е употребата на бърз вход и изход.

За GCC/MinGW сложи като първи ред в main нещо като cin.tie(0)->sync_with_stdio(0); ако все още не си го сложил и пробвай отново дали минава.

Аз лично бих я направил с нещо като Fenwick tree като маркирам началото на група с 1 а вътре в подстринговете слагам 0. По този начин за заявки от тип 1 по префиксна сума намирам индекса на групата на произволна позиция i за O(log N) и също заявки от тип 2 са ми O(log N) операция да update-на Fenwick дървото (то си е един прост масив, но това е друга тема).

Принципно при наивно решение проблем ще са ти заявките от втори тип (update), защото може да имаш дълги подстрингове, които като се разцепват на две *всички* индекси от втората част трябва да ги update-ваш, а те може да се милиони т.е. заявки тип 1 са ти O(1) докато заявки тип 2 са ти O(N) операция.

Примерно започваш от стринг от милион A-та, следват милион заявки от вида 2 1, 2 2, 2 3, ..., 2 1000000 и това означава че ще трябва да направиш 10^12 update-и, което няма как да мине на произволен judge.

cheers,
</wqw>

Това мнение е било редактирано от wqw на 02-06-2023, 13:59