12 random-ish max testów: [tu były trochę popsute testy, mniej popsute niżej]

Chyba nie są najmocniejsze, ale lepsze takie niż żadne. Ktoś coś?

Potwierdzam

Czy można by prosić o kilka małych testów?

Wydaje mi sie ze w kilku testach nie spelnione sa zalozenia z tresci, ze x1 <= x2 i y1 <= y2 (np. big12.in linijka 99891: "300000 12310 299999 12313"), dla niektorych z m-operacji. Dla wszystkich testow parzystych big(2|4|6|8|10|12).in, nie sa te warunki spelnione. Moge potwierdzic nieparzyste testy za to :)

@Michał: Ups, faktycznie.

To teraz bardziej poprawne testy, plus kilka małych:

small (5k, wszystko w przedziale [10, 20]): https://easyupload.io/qdgium
medium (100, wszystko w przedziale [1k, 2k]): https://easyupload.io/gttzdi
big (12, wszystko 300k): https://easyupload.io/k10fui

Jeśli mnie wzrok nie myli, to np w teście small44.in m = 10, a jest podane 11 prostokątów. W teście small2 podobnie :c I pewnie w wielu innych

Eh te parzyste testy, w każdym z nich jest m o jeden za małe xD

Podmieniłem te linki w poście wyżej, może teraz już testy spełniają specyfikację wejścia...

Potwierdzam wszystkie testy.

Jakie macie max czasy na tych testach? U mnie lokalnie max 2.3s, na SIO pewnie z 2x dłużej...

Mam 1.7s lokalnie, na SIO pewnie więc koło 4s

Może ktoś zechce się podzielić rozwiązaniem? Ja doszedłem do punktu gdzie moje (niepoprawne) rozwiązanie umiało przejść wszystkie testy z forum w <6s. Ciekawi mnie jak to się robiło poprawnie.

Z twierdzenia Halla (czy tam jakiegoś jego uogólnienia) wiemy, że jeśli rozważymy wszystkie pozbiory jedynek, dla każdego weźmiemy zera z którymi są połączone, i znajdziemy maksymalny "niedomiar" (liczba jedynek minus liczba zer), to wynikowy matching całości będzie mniejszy od pełnego matchingu o właśnie tyle.

Teraz zauważamy, że jedyne zbiory jedynek jakie warto brać pod uwagę są postaci: weźmy podzbiór wierszy, podzbiór kolumn, i rozważmy jedynki na ich przecięciu. Do tego jeśli dla wierszy i kolumn zapiszemy ile w nich jest jedynek, i posortujemy oba ciągi malejąco, to interesują nas tylko ich prefiksy (R wierszy o największej liczbie jedynek i odpowiednio C kolumn).

Dalej zauważmy, że dla ustalonego R optymalnie jest brać kolumny dopóki nie trafimy na kolumnę o mniej niż n-R jedynkach. A więc dla każdego R utrzymujemy pewne optymalne C[R], które rośnie wraz z R, i wynik uzyskiwany przez parę (R, C).

Gdy przychodzi update, te wszystkie struktury zmieniają się albo na O(1) pozycji, albo ewentualnie coś dodajemy/odejmujemy na sufiksie, co łatwo załatwiamy drzewem przedziałowym. Trzeba jeszcze zbudować te wszystkie rzeczy (sumy w wierszach/kolumnach, etc) dla początkowego stanu planszy, ale to już standardowe (zamiatanie z leniwym drzewkiem z operacją "flip bitów na przedziale").

Ja robiłem podobnie jak @Krzysztof, tylko jakoś dziwnie skminiłem tę część:
"Dalej zauważmy, że dla ustalonego R optymalnie jest brać kolumny dopóki nie trafimy na kolumnę o mniej niż n-R jedynkach. A więc dla każdego R utrzymujemy pewne optymalne C[R], które rośnie wraz z R, i wynik uzyskiwany przez parę (R, C)." i nie umiałem update'ów robić na drzewie przedziałowym, więc robiłem na jakiejś strukurce pierwiastkowej pewnie bardzo podobne operacje i w sumie miałem O(m log n+ q sqrt(n)) które zmieściło się w limitach czasowych.