#PQJ2022x10629. QOJ 2022_10629
QOJ 2022_10629
Zadanie: RZE Rzeki XXIX OI, etap III, dzień pierwszy. Plik źródłowy rze.* Dostępna pamięć: 128 MB. 6.04.2022 Dopiero gdy zostanie ścięte ostatnie drzewo, ostatnia rzeka zatruta, a ostatnia ryba złapana, człowiek odkryje, że nie naje się pieniędzmi. – przysłowie indiańskie W Bajtocji jest n rzek płynących z południa na północ wzdłuż prostych x = i dla (i = 1, 2, . . . , n) oraz m rzek płynących z zachodu na wschód wzdłuż prostych y = j (dla j = 1, 2, . . . , m). Na każdym przecięciu rzek znajduje się miasto. W każdym mieście jedna rzeka przebiega tunelem i nie miesza się z drugą. W przeszłości każde miasto czerpało wodę z rzek, nad którymi leżało. Niestety w dzisiejszych czasach niektóre rzeki są zanieczyszczone w stopniu uniemożliwiającym uzdatnienie wody, więc miasta muszą dostarczać wodę z innych rzek. Koszt dostarczenia wody z rzeki do miasta jest równy odległości miasta od prostej, wzdłuż której płynie rzeka. Do przewozu wody używane są ciężarówki jadące dwukierunkowymi drogami położonymi wzdłuż rzek (nie ma znaczenia, w którą stronę płynie rzeka, z której do miasta dowożona jest woda). Niestety Bajtocja dysponuje ograniczonym budżetem i może nie być w stanie dostarczyć wody do wszystkich miast. Sytuację komplikuje fakt, że niektóre rzeki zostają oczyszczone, a niektóre ponownie zanieczyszczone. Napisz program, który wczyta aktualny stan rzek oraz umożliwi wykonywanie akcji dwóch typów: zmiana stanu rzeki oraz odpowiedź na zapytanie o maksymalną liczbę miast, do których da się dostarczyć wodę przy zadanym budżecie. Wejście W pierwszym wierszu wejścia podane są trzy liczby całkowite n, m i z (1 ≤n, m, z ≤100 000) oznaczające kolejno: liczbę rzek płynących w kierunku północnym, liczbę rzek płynących w kierunku wschodnim oraz liczbę akcji do przetworzenia. W drugim wierszu znajduje się słowo długości n złożone ze znaków + i - (plus i minus); i-ty znak ozna- cza stan i-tej rzeki płynącej na północ: znak plusa oznacza rzekę czystą, a znak minusa – zanieczyszczoną. W trzecim wierszu znajduje się słowo długości m opisujące początkowy stan rzek płynących na wschód, w ana- logicznym formacie. W kolejnych z wierszach znajdują się opisy akcji w jednym z następujących formatów: • Z c – zapytanie o maksymalną liczbę miast, do których można dostarczyć wodę, dysponując budżetem c (0 ≤c ≤1018), • N i – informacja że i-ta rzeka płynąca na północ zmienia swój stan, czyli jeśli była czysta, to staje się zanieczyszczona i odwrotnie (1 ≤i ≤n), • M i – informacja że i-ta rzeka płynąca na wschód zmienia swój stan (1 ≤i ≤m). Wyjście Dla każdego zapytania typu Z z wejścia należy wypisać w osobnym wierszu jedną liczbę całkowitą, oznaczającą maksymalną liczbę miast, do których będzie można doprowadzić wodę. Olimpiada Informatyczna (oi.edu.pl) 1/2 Rzeki (v. 1.2) Olimpiada Informatyczna finansowana jest ze środków Ministerstwa Edukacji Narodowej w ramach zadania publicznego „Organizacja i przeprowadzenie olimpiad i turniejów w latach szkolnych 2019/2020, 2020/2021, 2021/2022”. Przykład Dla danych wejściowych: poprawnym wynikiem jest: 3 4 11 11 --+ 9 +++- 0 Z 1 10 M 1 12 M 2 M 3 Z 7 N 3 Z 1000000000000000000 M 2 N 2 Z 4 Z 1000000000000000000 Wyjaśnienie przykładu: Poniższy rysunek obrazuje sytuację przed wykonaniem akcji. Liniami ciągłymi oznaczone są rzeki czyste, zaś liniami przerywanymi rzeki zanieczyszczone. Jest 12 miast na przecięciach tych linii. 4 3 2 1 1 2 3 Odpowiedzią dla pierwszego zapytania (Z 1) jest 11, ponieważ koszty doprowadzenia wody do miast (1, 4) oraz (2, 4) są równe 1 (stąd jedno z nich musi pozostać bez dostępu do wody), a koszty doprowadzenia wody do pozostałych dziesięciu miast są równe 0. Po wykonaniu drugiej akcji (M 1), miasta (1, 1) oraz (2, 1) tracą bezpośredni dostęp do rzeki, analogicznie po wykonaniu trzeciej i czwartej akcji bezpośredni dostęp do rzeki mają już tylko cztery miasta. A zatem odpowiedź na kolejne zapytanie (Z 7) jest równa 9, bo w ramach budżetu 7 można zapewnić dostęp do wody jeszcze czterem miastom leżącym na prostej x = 2 oraz jednemu miastu leżącemu na prostej x = 1. Testy „ocen”: 1ocen: n = m = 11, czysta jest szósta rzeka na północ i szósta rzeka na wschód; zapytania o koszty 0, 1, . . . , 220; 2ocen: n = 100 000, m = 1, przy zapytaniu zawsze jest dokładnie jedna czysta rzeka (tzn. dla 1 ≤i ≤33 333 najpierw oczyszczana jest rzeka 3i, potem następuje zapytanie o koszt 2 500 000 000, a na końcu rzeka 3i jest z powrotem zanieczyszczana). Ocenianie Zestaw testów dzieli się na następujące podzadania. Testy do każdego podzadania składają się z jednej lub więk- szej liczby osobnych grup testów. Podzadanie Warunki Liczba punktów 1 n, m, z ≤100 7 2 każda rzeka płynąca na wschód jest zawsze zanieczyszczona 7 3 n, m, z ≤1000 21 suma budżetów w zapytaniach nie przekracza 109 4 21 5 brak dodatkowych ograniczeń 44 Olimpiada Informatyczna (oi.edu.pl) 2/2 Rzeki (v. 1.2) Olimpiada Informatyczna finansowana jest ze środków Ministerstwa Edukacji Narodowej w ramach zadania publicznego „Organizacja i przeprowadzenie olimpiad i turniejów w latach szkolnych 2019/2020, 2020/2021, 2021/2022”.