@Tomek Czajka niestety raczej nie wejdzie, mam identycznie (też grupuję) i pomimo że maxtesty na zwykłym /usr/bin/time wychodziły blisko limitu, to na sio (sprawdzane skryptem oiejq ze strony OIa) już przy n=q=100k wychodziło powyżej 100 sekund. Niewykluczone że gdzieś zepsułem grupowanie, bo przy dużych losowych testach odrzucało mi tylko około połowy zapytań.

Swoją drogą moim zdaniem wymyślenie rozwiązania bez dowodu wydaje mi się dość dziwne. W sensie trochę nie wiem jaką ścieżką rozumowania można krążyć aby wpaść na te warunki co trzeba i jednocześnie nie być bardzo blisko pełnego dowodu. Chyba że ktoś pisał jakieś wykładniki i gapił się na outy i dopasowywał, to wtedy rzeczywiście można być zupełnie nieświadomym o co chodzi w zadaniu, a jednak dostać 10/10

Ja miałem 3 samochody, które pędziły sobie 3 liniami. Następnie sprawdzałem w czasie stałym, które zdarzenie nastąpi jako pierwsze: któryś z samochodów będzie musiał zwolnić; któryś z samochodów będzie mógł zjechać na inny pas. Następnie przechodziłem do tego wydarzenia i obsługiwałem. Jeśli jakiś samochód mógł zjechać na pas obok, to sprawdzał najpierw czy w ten sposób wyprzedzi samochód który już tam się znajduje i jeśli tak to zastępuje go, jednocześnie zostając na swojej linii (zostaje skopiowany).

Rozwiązanie choć wydawało mi się proste w koncepcji było bardzo brzydkie do implementacji. Nie udało mi się go zdebugować i nie wiem czy w algorytmie był błąd czy w implementacji.

Zgadzam się, że zadanie było istotnie najtrudniejszym z dywizji C. Aczkolwiek 4B było dla mnie istotnie trudniejsze. Szczególnie biorąc pod uwagę, że to zadanie kodziło się parę minut, a 4B z godzinka przynajmniej

Ale jest też trochę trikowa interakcja między lewym pasem a prawym. Czasem może być tak, że przerwa po prawej stronie jest zbyt krótka, żeby się w niej zmieścić, ale jak szybko ominiemy lewą stroną, to jeszcze wykorzystamy tą samą przerwę po prawej dalej.

Ja miałem dość proste O((n+q)n^(2/3)).
Brutalny dynamik idze tak: dp[i][j]=max(dp[i+1][j],dp[i+k][j]+A[i]+...+A[i+k-1]).

Niech S=n^{1/3}
Licze tego dynamika tylko dla i takich że
1. (i mod k) mod S = S-1
lub
2. i/k mod S= S-1

Jeżeli mam zapytanie (i,j) i chce dostać dp[i][j] dla niepolicznego i puszczam takiego jakby bfs-a, ze chce znac odpowiedz dp[i+1][j] i dp[i+k][j].
Widac, że bfs-em odwiedze co najwyzej S^2 stanów zanim dojdę do już policzonych, a dynamika musze policzyć dla co S-tego i. Sumarycznie mam O(n^(5/3)+qn^(2/3)).

Ja chciałem powiedzieć, że rozwiązując to zadanie najbardziej dumny byłem z siebie w momencie, gdy wpadłem na pomysł jak je testować lokalnie. Mianowicie logika do jeżdżenia górą była zupełnie inna niż do jeżdżenia dołem, więc pomyślałem, że zrobię dwie wersje kodu - jedna, w której zabronię jeździć górą i jedna, w której zabronię jeździć dołem i będę porównywać ich outy na odpowiednio przesuniętych testach :P

Również bardzo serdecznie dziękuję za Potyczki 2021. Było mi bardzo miło powrócić do lat liceum, ostatni raz na serio chyba brałem udzial w 2016 :)
Przedawkowałem matematyczne contesty na codeforces i atcoderze, więc brutalne kodzenie starych dobrych struktur danych było jak powiew świeżości.

Pomijając same zadanie, sądzę że testy do zadania skrzyżowania nie były dobre. Udało mi się otrzymać 10 punktów za dwa zgłoszenia z następującymi błędami, które sam sobie ubiłem na testrunie, itp.:
1) zgłoszenie z błędnie (pod względem cache) ustawionymi wymiarami w tablicy jump-pointerów dostawało TLE na testrunie na prostym teście z dużym inputem oraz N opisanym w następnym punkcie
2) zgłoszenie, w którym założono że maksymalna różnica wyniku od czasu zapytania (czyli to ile będziemy iść) to MAX(N, M). Wystarczyło zrobić test z N = 15000 oraz naprzemiennie 01010101 i 10101010 w kolumnach i to zgłoszenie już dostawało WA.

Sądzę że to są dosyć poważne błędy i takie zgłoszenia nie powinny dostawać 10 punktów, ponieważ mają one błędne założenia o ważnych stałych w zadaniu lub po prostu nie wyrabiają czasowo na ekstremalnych inputach. Dla ludzi z dostępem napiszę też numery zgłoszeń.
1) 499166 i testrun 499194
2) 499253

Pozdrawiam

Ja mam O(n^(5/3 + eps)) zakładając n ~ q.
Dla "małych k" można proste divide and conquer w nk log n.

Dla większych k taka obserwacja:
- Załóżmy że mamy wyniki dla wszystkich przedziałów [x, y], gdzie y % k == 0
- wtedy w O(nr / k) możemy policzyć wynik na przedziale [x, y], gdzie y % k == r, bo rekurencja nam zmniejsza resztę o max 1, czyli musimy przeliczyć r - 1 reszt * n/k kroków, które wykonujemy cofając się o k do tyłu.

Z reszt 0..k-1 wybieram k/l reszt w odległościach ~l i dla każdej z nich liczę dynamikiem odpowiedzi dla wszystkich początków. To robimy w czasie O(n * n/k * k/l) = O(n^2 / l). Zapytania realizujemy w O(nl / k) per zapytanie.
Biorąc l = k^(1/2) daje nam to alg działający w O(n^2 / k^(1/2)).

Optymalne k do wyboru między d&c, a tym drugim dziwactwem to k=n^(2/3 - eps), ale w praktyce d&c było trochę szybsze, więc ja przyjąłem k=1500.

Ja mam O(n*k*log n) za pomocą dziel i zwyciężaj.

Ja mam n^3/2.
Kluczowy pomysł zadania jest taki, aby z zadania jednowymiarowego zrobić dwuwymiarowe... Tzn. jak mamy nasz graf przejść skaczący co 1 i co k, to on tak naprawdę topologicznie jest takim jakby ... spiralnym walcem. Tzn zmapujmy barierę pomiędzy (i-1)-szą i i-tą liczbą na pole o współrzędnych (i%k,i/k) (dzielenie całkowite oczywiście). Wtedy mamy strzałki z pola (a, b) do (a+1, b) o zysku 0 i do pola (a, b+1) o zysku "suma na którymśtam przedziale o długości k". Przy czym są jeszcze strzałki (k-1, i) do (0, i+1) (skąd to jakby walcowate sklejenie z przesunięciem). I nasze zadanie zamienia się w pewnym sensie dwuwymiarowego dynamika na planszy o wymiarach k x (n/k), tzn. każde zapytanie to pytanie o najdroższą ścieżkę pomiędzy jakimiś dwoma wierzchołkami na tej planszy. Jego można już rozwiązać przez dziel i rządź.
W prostszej wersji, gdy wybieramy sobie krótszy bok (co jest zależne od tego czy k jest mniejsze czy większe niż sqrt(n)) i tniemy w połowie po odpowiednim zawsze tym samym wymiarze. To da O(n^3/2 log n). W trudniejszej wersji możemy w każdym kroku patrzeć, który bok jest aktualnie krótszy (tzn raz tak raz siak), co daje n^3/2. Aczkolwiek te krawędzie (k-1, i)->(0, i+1) dodają sporo syfu i w szczególności deduplikacja kodu jest niezbyt możliwa, bo przynajmniej u mnie cięcia pionowe i poziome się sporo różniły.

Też mam O(qn), tylko grupuję zapytania tak, żeby unikać liczenia dwa razy zapytań o tym samym końcu (którymkolwiek).

Być może miało na celu nauczenie ludzi, że czasem lepiej napisać brute'a i popatrzeć na outy niż kminić dowód
EDIT: a czy wymyślenie rozwiązania bez wyraźnej wskazówki jaka jest odpowiedź jest trudne, to nie wiem bo nawet nie próbowałem

@Piotr niekoniecznie, u mnie brut który dfsował się po grafie wszystkich osiągalnych stanów zajmował 26 linijek kodu + wczytywanie danych. Co ciekawe, wykręcał całe 3 punkty.