Jak robiliście to zadanie? Udało mi się przekształcić każdą minę do postaci "przedział indeksów min które ostatecznie wybuchną jeśli wysadzę tę minę" i próbowałem robić dynamika/zamiatanie na wierzchu, ale nic mi z tego nie wyszło.

Moje rozwiązanie było dość toporne, ale:

Faza pierwsza
1. Dla uproszczenia najpierw konwertuję miny z promienii do zakresów min detonowanych przez daną minę, wyszukiwaniem binarnym
2. Dla każdej miny szukam najbliższej miny po lewej i prawej, która rozważaną minę zdetonuję. Z tego powstaje graf.
3. Łączę cykle w pojedyncze wierzchołki (używając find/union) – dostajemy DAG.
4. Idąc w kolejności topologicznej możemy teraz policzyć jakie miny zostaną *rzeczywiście* zdetonowane przez każdą minę – aktualizuję zakresy z punktu 1. Dostajemy listę par (a,b) (o liczności <=n, bo część została połączona w fazie 3)

Faza druga:
1. Najpierw Sortuję pary/miny po rosnącym a, dla tych samych a po *malejącym* b. Dla każdej miny chcemy policzyć na ile sposobów można odpalić eksperyment tak, że ta mina jest odpalona, ale nie jest odpalona żadna późniejsza.
2. Tworzę drzewo przedziałowe, które potrafi szybko zwracać sumę wszystkich zawartych liczb w ciągu od indeksów 0 do podanego n. Na początku wszystkie wartości w ciągu to zero.
3. Ustawiam wartość w drzewie dla 0 na 1 (bo dla pustego zbioru min jest jedna kombinacja)
4. Przechodząc po kolei posortowane pary (a,b): liczę sumę wszystkich liczb w ciągu poniżej b (czyli na ile jest różnych eksperymentów takich, że odpalone są tylko miny o a1<a i b1<b). Nasz ciąg zwiększamy o tą wartość na pozycji b.
5. Suma wszystkich wartości w ciągu to wynik.

Wydaje mi się, że dałoby się bez drzewa przedziałowego, ale nie wykminiłem jak :).

Zakładając, że już w pierwszej fazie obliczyliśmy:
lewo(n) = jak daleko sięga reakcja łańcuchowa w lewo
prawo(n) = jak daleko sięga reakcja łańcuchowa w prawo

Następnie obliczamy:
poprzednia(n) = największe m < n takie, że prawo(m) >= n

Można to zrobić jednym przejściem po minach od lewej do prawej, utrzymując stos min o rosnącym m i malejącym prawo(m).
Jeśli robiliśmy fazę 1 świetną metodą Marcina to mamy to już policzone wcześniej.

I teraz możemy rekurencyjnie obliczyć:
ile(n) = na ile sposobów można pobawić się prefiksem zakończonym miną n
odpalamy(n) = na ile sposobów można pobawić się prefiksem tak, żeby odpalić ostatnią
nie_odpalamy(n) = na ile sposobów można pobawić się prefiksem tak, żeby nie odpalić ostatniej

ile(n) = odpalamy(n) + nie_odpalamy(n)
odpalamy(n) = ile(lewo(n) - 1)
nie_odpalamy(n) = ile(n - 1) - odpalamy(poprzednia(n))