Potwierdzam.

Potwierdzam

Potwierdzam :)

Również potwierdzam

Potwierdzam

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 :).

Potwierdzam.

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.

Potwierdzam

Potwierdzam, można iść spać. :)

Nie potwierdzam. Bo nie zrobiłem.

Potwierdzam

potwierdzam bo zdebugowalem i działa

Potwierdzam testy Anadiego

Potwierdzam