To jak się robi to zadanie? Miałem różne obserwacje ale żadna specjalnie mi nie pomogła z faktem że jest milion różnych zapytań :P

Kluczowa obserwacja: przez ulicę można przejść bezpośrednio na drugą stronę, z wyjątkiem sytuacji, gdy wszystkie światła przez tą ulicę są czerwone.

Druga kluczowa obserwacja to że w każdej iteracji bajtocję da się podzielić na X pasów poziomych lub pionowych (zależnie od konfiguracji), gdzie wszystkie place w obrębie pasa są dostępne. Być może X=1 i wtedy każda podróż odbędzie się w czasie 0.

Mi zabrakło pomysłu, jak obejść długie ciągi tego samego typu (tylko pionowe, tylko poziome). Bo jak tylko pasy zmienią kierunek, to od razu można dojść do punktu docelowego.
Więc miałem bruteforce gdzie wyliczyłem wszystkie pasy - liczba iteracji to NWW(długość iteracji każdego skrzyżowania) - i symulowałem każde przejście dla czasu modulo NWW. Rozwiązanie takie dało 3/10.

Ta obserwacja inaczej sformułowana to "spójne składowe w każdym momencie to albo poziome pasy albo pionowe pasy"

Tak jak wspomniano wyżej, pierwsza obserwacja jest taka, że z danego punktu można przejść w dowolnym kierunku jeśli nie jest zablokowana cała ulica pionowa/pozioma.
Obserwacja nr2: Nie ma sytuacji w której ulica pionowa i ulica pozioma są zablokowane w tym samym momencie(na jakimś skrzyżowaniu wtedy świeciłyby się 4 czerwone światła), czyli w danym momencie plansza jest podzielona na pionowe/poziome paski w których możemy się swobodnie przemieszczać.
Obserwacja nr3: Układ świateł powtarza się co 840 (840 = NWW(1,2,3,4,5,6,7,8)), możemy więc wyznaczyć dla każdej ulicy czy jest zablokowana w każdym momencie modulo 840(czyli czy jest zablokowana jeśli czas % 840 wynosi 0, potem 1, 2...839) w czasie O(n*m*8 + (n+m)*840*8)

Przejdźmy do odpowiadania na zapytania. Jeśli w momencie początkowym zapytania nie jest zablokowana żadna ulica to od razu możemy się przemieścić. Jeśli zablokowane są ulice poziome, to na początku możemy się ustawić nad/pod punktem końcowym i teraz interesuje nas tylko przesuwanie się w górę/dół. Mamy teraz punkty postaci (x,t), czyli wysokość na jakiej się znajdujemy i czas % 840, dla każdego takiego punktu możemy wyznaczyć jak najdalej jest w stanie przemieścić się w górę/dół w trakcie trwającej minuty (jest w stanie się przemieścić dopóki nie napotka poziomej zablokowanej ulicy). Jesteśmy w stanie wyznaczyć to w czasie O((n+m)*840).
Żeby teraz odpowiedzieć na pytanie zastanawiamy się, ile razy musimy skoczyć za pomocą tej znalezionej wartości. Żeby nie musieć tego symulować możemy użyć triku z LCA, czyli wyznaczyć w jakim miejscu znajdziemy się po 1,2,4,8,... skokach i binsearchować dla każdego zapytania.
Złożoność na wygenerowanie tych skoków to jakieś O((n+m)*840 * log(n)), złożoność na zapytania to O(q*log(n)). Trzeba jeszcze uważać na pamięć, tablica tych skoków zajmuje jej całkiem sporo. Rozwiązaniem jest pogrupowanie zapytań według tego czy będziemy chcieli skakać w lewo/prawo/górę/dół i dla każdej grupy najpierw przygotować te wartości a potem odpowiadać, możemy wtedy cały czas korzystać z tych samych tablic i ilość pamięci spada czterokrotnie.

Jak już wiesz, że masz tylko poziome albo tylko pionowe pasy, to wiesz, że ruszanie się pionowo i poziomo jest niezależne - tj. jak masz przejść z (A,B) do (C,D), to albo od razu możesz przejść do (C,B) albo od razu do (A,D). Więc zadanie robi się jednowymiarowe.

To teraz chcemy wiedzieć, ile zajmie przejście w poziomie z A do C, jeśli zaczynamy w chwili T (modulo NWW). I tu liczymy logarytmiczne skoki - dla każdego T (od 0 do NWW-1), dla każdego i (od 0 do 20), dla każdego N (od 0 do maxN / 2**i) chcę wiedzieć, ile zajmie przejście z N * 2**i do (N+1) * 2**i jeśli zaczynam w T (mod NWW). Oblicza się całe D w czasie NWW * MAXN * 2, bo każdy skok długości 2**i rozbija się na dwa skoki długości 2**(i-1) (przy czym ten drugi zaczyna w czasie przesuniętym o czas wykonania pierwszego skoku). I teraz każde zapytanie rozbija się na max 2 logN skoków długości 2**i, czyli pojedyncze zapytanie obsługuję w logN.

Irytujące detale:
* D jest inne jeśli idę w przód, a inne, jeśli idę w tył, czyli muszę policzyć i to, i to (ja w sumie miałem cztery tablice: pion/poziom, przód/tył).
* Na początku trzeba policzyć dla każdej ulicy, czy da się przez nią przejść w danym czasie, co naiwnie jest N * M * NWW. Nie byłem pewien, czy to się zmieści, więc wszystko pozmieniałem na bitmaski, i mam na początku N * M * NWW / 64.

Czyli łączna złożoność: (N * M * NWW / 64 + max(N,M) * NWW + Q log N). Czasy dochodzą do 4.7 / 9.

@Jan Klimczak ciekawostka:
Trzymałem dokładnie to ale na vectorach shortów, pamięciowo się mieściło, ale czasówki przekroczone (różne submity dostawały 5-7 punktów)

> Na początku trzeba policzyć dla każdej ulicy, czy da się przez nią przejść w danym czasie, co naiwnie jest N * M * NWW

Można osobno liczyć patterny mod 2, 3, ... 8 dla każdej ulicy, i dopiero na koniec zamienić na pattern modulo 840 dla całej ulicy.

Opcja pośrednia: liczyć patterny modulo 24 i modulo 35.

@Marcin Mordecki Początkowo zrobiłem też vector<vector<vector<uint16_t>>>, ale najgłębszy wymiar był odpowiedzialny za skoki o 2^k, więc był krótki i do każdych 20-30 bajtów dokładało 24 bajty z samego konteenera:-) Zdązyłem walnąc prostą tablicę 3d, zapisująca w liniowej przestrzeni, nawet ustawilem wymairy tak, by praktycznie zawsze iterowało w najglebszej pętli po nahjglebszy wymiarze. Ale ~ polowa czasów zleciała.
Wszystko praktycznie identycznie jak opowiadający wyzej, cztery tablice n*840*liczba_poziomów. Pamieci starczało dla liczby poziomów >17.
Nie rozrózniałem przypadków testowych na kategorie (co też nie przeszkadza, bo jak zapytam tabelki o )ten drugi wymiar, ta od razu odpowie, że doszedłem w tej wspolrzednej.
Dla liczby poziomów = 11 dstało 6 punktów. Ale ostatecznie wysłałem z liczba poziomów 15, co na moim kompie i testach dawało lepsze wyniki, ale wtedy dostało 4. Będę musiał kiedyś popatrzeć, co tak niewydajnie robiłem. Trzeba było optymalizować, a nie "ponizej 8 sekund u mnie, to na sprawdzazrce się zmieści" :)

Ja tam mam złożoność O(8mn+840*8*(n+m)+q), a i tak 7.2s/9 mi zabrało. Aby mieć q, a nie jakie q log n, to ogólnie to jak sobie pomyślę o jednowymiarowym zadaniu, że idę w prawo i mam stan (i, t), tzn. jestem na polu i oraz reszta z dzielenia czasu przez 840 to t, to jak przejście do i+1 jest zablokowane, to idę do stanu (i, (t+1)%840), a jak nie to (i+1, t). Takie krawędzie tworzą las z 840 korzeniami postaci (m, t), ale zamiast po nim obskakiwać jumppointerami zgodnie z kierunkami krawędzi, to zapuszczam dfsa po grafie odwróconym i jak wchodzę do wierzchołka (i, t) to patrzę jakie są zapytania, które się zaczynają w takim stanie i po prostu odczytuję ile krawędzi typu (i,t)->(i, (t+1)%840) przeszedłem od czasu wyjścia z warstwy j, gdzie j to punkt docelowy danego zapytania.

A żeby nie mieć O(mn*840), to dla każdej ulicy pionowej, to na początek dla każdego L liczę ora cykli świateł o długości L i dopiero jak już je mam, to wtedy wyliczam całościowy pattern w czasie O(840*8)