Minął tydzień, drugi, a niedługo minie trzeci. Obiecałem więc acz niechętnie piszę
Jaki czas wydaje Ci się nie najgorszy? : http://pl.spoj.com/status/FR_02_13,redysz/ Czas 0.02 zgłoszenia nr 19826638, czy może czas 0.22 ostatniego zgłoszenia? Przecież jeżeli masz błędną odpowiedz, to ten czas jest też błędny [dotyczy tylko pierwszego[ych] testu[ów]
Przecież nawet na ideone, dla twojego malutkiego teściku [n=tylko 101] już masz czas 0.14.
Kolejność jest taka: najpierw uzyskaj AC, a potem baw się optymalizacjami, ulepszaczami i przyśpieszeaniem swojego programu. W tym wypadku wiesz jak zrobić program - drzewo maximów + zwykłe sito + wzbogacenie tabeli liczb pierwszych.
PS
Jeżeli chodzi o twój zamieszczony program, to czy warto szukać tam błędu? I tak będzieTLE. jEŻELI KONIECZNIE JEDNAK CHCESZ GO ZNALEŹĆ LUB PROSIĆ O POMOC W ZNALEZIENIU [sorry caps się włączył] błędu to uprość kod. W tej chwili masz tam i bruta i swoją implementrację kodu napisanego w pythonie. Czy wiesz czym w pythonie jest S = {} ?
PS 2
Czym jest wzbogacona tabela liczb pierwszych? [ma to w algorytmice swoją nazwę, ale w tej chwili nie pamiętam]
Zwykła tablica liczb pierwszych:
0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 ...... itd
lub [odwrotnaa]
1 1 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0
wzbogacona [np liczymy ile jest liczb pierwszych od początku:]
0 0 1 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 77 7 7 7 8
dla naszego zadania "wzbogacamy" inaczej:
1 2 0 0 1 0 1 0 1 2 3 0 1 0 1 2 3 0 1 2 3 4 5 0 .... itd
Dla dowolnego wybranego fragmentu takiej nasze wzbogaconej tablicy, może wystąpić np:
.... 0 1 2 3 4 5 0 1 0 1 2 3 4 5 6 7 ....
Interesuje nas pogrubiony przedział.
z fragmentu 0 1 0 1 2 3 4 5 max obliczamy drzewem, ale dodatkowo musimy "ręcznie" sprawdzić lewy fragment
Inny przykład:
.... 0 1 2 3 4 5 6 7 8 9 10 0 1 0 1 2 3 4 5 6 7 ...
Powyżej drzewo analogicznie "podaje". maks 5, {0 1 0 1 2 3 4 5} ale ręcznie obliczamy lewy fragment, który tu wynosi 6.{5, 6, 7, 8, 9, 10}
AD PS
Sorry, na githubie, jest też kod w cpp, nie zauważyłem. W tym kodzie chodzi o zmniejszenie zużycia pamięci, ale dla małych n, kod jest wolniejszty [jak pisze autor] od zwykłego sita, więc w zadaniu lepiej po prostu nie kombinować i użyć zwykłego sita. A błąd, może porównaj swój kod z orginałem? Użycie long long czy uint64_t jest całkowicie zbędne. "Zwykły" zupełnie wystarcza do tego zadania [to oczywiście nie zmieni w cudowny sposób tle w AC].
PS 3
Aby "uzyskać przesiane" liczby pierwsze i "wzbogacić" uzyskaną tabelę o dodatkową informacje i tak "twój" kod z githuba na niewiele się przyda - odzielnie trzymana jest lista liczb pierwszych ii fargmentarycznie liczb złożonych [na bieżąco uzupełniana i odpowiednio zubożana-kasowana]