Problem z optymalizacja kodu do zadania Deszcz

Question

link do zadania : http://wklej.org/id/3226666/ (przepraszam że tu ale nie wiedzialem gdzie indziej moglem go wkleić) a tu jest mój kod: http://wklej.org/id/3226663/ dziekuję  i pozdrawiam

Answer 1

Zadanie deszcz jest częścią trwającego contestu :<
https://sio2.staszic.waw.pl/c/wwi-2017-konkurs-kwalifikacyjny/p/
Po contescie chętnie pomogę =))

Contest się skończył, więc oto podpowiedzi:
Twój program dla każdego zapytania przegląda wszystkie dni z opadami. Ma więc złożoność O( n * q ). Teraz dla największych danych ( n <= 10^5 i q <= 10^5 ) twój program wykona ~ 10^10 operacji, czyli będzie działał wiele minut.
Trzeba wymyślić inny, szybszy algorytm. Mogę podpowiedzieć, że dobre rozwiązania są dwa: oba działają w czasie liniowo-logarytmicznym, przy naszych ograniczeniach oznacza to, że są w porządku. 
W obu rozwiązaniach trzeba przenumerować zapytania i przedziały, na których pada deszcz, ponieważ oba rozwiązania trzymają komórki w pamięci dla każdego miasta z zapytań i opisów dni, więc można je wrzucić do tablicy, posortować i używać indeksów w tablicy posortowanej jako ich nowe numery, reszta miast jest nieistotna, dlatego to działa.
Pierwsze rozwiązanie to implementacja struktury, która nazywa się drzewo przedziałowe (segment tree), nie jest to za trudne, ale zadanie było w pierwszej grupie, dlatego istnieje inne, sprytniejsze rozwiązanie.
Mamy tablice, gdzie indeksy odpowiadają miastom (dlatego robimy przenumerowanie, żeby ta tablica miała co najwyżej 2 * 10^5 komórek, a nie 10^9, bo taka nie wejdzie). Powiedzmy, że spadło 8 jednostek deszczu na miasta od 10 do 12. Teraz możemy w mieście o indeksie 10 dodać 8, a w mieście o indeksie 12 + 1 = 13 odjąć osiem. Teraz jeśli po zrobieniu tak dla każdego dnia, możemy przechodzić po tablicy od 0 do końca i wykonywać następujący algorytm:
1. Suma += wartosc w tablicy w i-tym indeksie
2. odpowiedzi dla i-tego miasta = aktualna wartość sumy
3. I przechodzimy do następnego miasta
W ten sposób w każdym mieście na końcu jest zapisane, ile faktycznie spadło na niego deszczu i możemy wczytywać odpowiedzi i odpowiadać na nie natychmiast. Ten trick jest ważny i pojawił się m. in. na Olimpiadzie Informatycznej.

Trzeba też przyznać na koniec, że to dość bardzo trudne zadanie jak na innej w pierwszej grupie, ale warto próbować =]