Potwierdzam wszystkie testy.

potwierdzam wszystko

Potwierdzam i wrzucam 100000 małych losowych testów w postaci generatorki: https://drive.google.com/open?id=1gjJnisjIhqk_T_t4zs46sSqCJ7q1HNFb
Należy zmienić ścieżkę do swojego rozwiązania w trzeciej linijce. Na końcu skrypt wypisze hasz outputów. Mi wyszło 315772849.

Ja mam podobnie jak w rozwiązaniach z hashowaniem, ale do identyfikacji zbioru aktywnych przedziałów użyłem pary (ilość_aktywnych_przedziałów, minimalny_prawy_koniec_aktywnego_przedziału). Przy przeglądaniu początków i końców przedziałów w kierunku rosnących współrzędnych (dla różnych zbiorów aktywnych przedziałów) nie powinienem dostać kolizji takich par, więc użyłem ich jako klucze (po zrzutowaniu na long long) w mapie zliczającej wynik dla zbioru przedziałów. Do utrzymywania minimalnego prawego końca aktywnych przedziałów użyłem po prostu priority_queue.

Wrzucam trochę losowych testów.
https://drive.google.com/file/d/1vpyRA5QXHR-hIj2CvFrdoiWXwYWy9caz/view?usp=sharing

To ja jeszcze tylko dodam, że zrobiłem bardzo nieprzyzwoicie, czyli na double'ach, symulując rozlewanie herbaty od najgorętszego docelowego kubka, zakładając, że każdy docelowy kubek opłaca się wypełniać z kubków o najbliższej mu temperaturze.

Niestety źle ustaliłem numeryczny ε (1e-11), więc 9/10. Przy 1e-10 byłoby 10/10 :-)

@Lech Duraj: Robię mniej więcej w ten sposób właśnie. Korzystamy z tego, że sqrt(5)*F_n = x^n - (-x)^(-n), gdzie x to złoty podział. Zapisujemy liczby A i B używając tego jako wielomiany P i Q, t. że A*sqrt(5) = P(phi) i B*sqrt(5) = Q(phi). Będą one "palindromiczne" z tym, że przy ujemnych wykładnikach mamy przemnożenie przez +-1. Po wymnożeniu ich używając FFT dostajemy wielomian PQ, który spełnia A*B*5 = PQ(phi). Dzielimy PQ przez "sqrt(5)", czyli wielomian x^2 - x^(-2) i otrzymujemy A*B*sqrt(5). Jeśli "dobrze" zrobimy to dzielenie to dostaniemy znów "palindromiczny" wielomian i żeby wrócić do postaci Fibonacciego wystarczy wziąć współczynniki przy dodatnich wykładnikach.

Potwierdzam

U mnie też hashowanie, tylko zamiast Zobrista użyłem mnożenia liczb pierwszych modulo P=4294967029.
Wchodzimy do odcinka — mnożymy przez p. Wychodzimy z odcinka — mnożymy przez odwrotność p modulo P.

Po prawdzie to nie próbowałem tego klepać, ale czy nie zadziałałoby coś takiego?

Wiadomo, że F_n = q^n - (1/q)^n, gdzie q = 1+sqrt(5)/2, jeszcze razy jakaś nieistotna stała. Ale w takim razie można zapisać liczbę w systemie Fibonacciego jako W(q)-W(1/q), gdzie W jest wielomianem. Co jest równoważne W*(q) / q^n, gdzie W* jest wielomianem, który ma najpierw współczynniki W, a potem te same w odwrotnej kolejności.
No to pomnożenie dwóch takich wielomianów da się zrobić jednym FFT. A potem jeszcze trzeba wrócić z powrotem do systemu Fibonacciego - ale jeśli się nie mylę, iloczyn znowu będzie wielomianem "palindromicznym", więc powrót będzie bardzo łatwy.

@Tomek Czajka - tak w skrócie, jak zmieniało się szybko(nie O(n^2)) na binarny?

Do ludzi, którzy mają 7/10. TLE na 2a, 8f, 9f?

Potwierdzam

potwierdzam

potwierdzam, aczkolwiek mój naiwniak kręcił test B1 przez 50 minut