BAJTIOS1 - Bajtocki Inspektorat Ochrony Środowiska 1

[odzwp]

witam, ma ktoś pomysł na przyspieszenie tego kodu?
kod:
zadanie:https://pl.spoj.com/problems/BAJTIOS1/

[eksekk]

Jest pewien sposób, dzięki któremu można obliczać zapytania typu “suma liczb o indeksach od a do b” w czasie stałym O(1). Najpierw może spróbuj sam wpaść na niego (wskazówka: używając tego sposobu każda zmiana liczby dzieje się w czasie liniowym O(n) zamiast zwykłego O(1)). Jeśli nie uda Ci się, to pogoogluj. Jak nadal nic nie znajdziesz, napisz tutaj. I nie denerwuj się jak nie zrozumiesz/znajdziesz, mi też to na początku sprawiło kłopot i musiałem znaleźć ten sposób w internecie.

[narbej]

0. “ma ktoś pomysł na przyspieszenie tego kodu?” Nie tym sposobem, ale nie mogłem się powstrzymać od wytknięcia :
1. Jeśli zaczynasz, przeczytaj koniecznie! <--kliknij w to proszę!
2. AD 1. http://discuss.spoj.com/search?q=%20%20BAJTIOS1
3. Użycie w kodzie: "ios_base::sync_with_stdio(0);" a potem "cout << .... << endl" <---- znaczysię był na lekcji ale nie uważał?
4. Użycie: vector <doble> do pamiętania wartości 0 / 1 [true/false]
5. Nazwy zmiennych, funkci itd owszem powinny opisywać ale musi to być kompromis, między długością nazwy a rozwlekłym opisem. Np a, b, numberOfInquiries czy thePermissibleLevelOfContamination, numberOfInquiries. To jest temat rzeka, dobrym żródłem wiedzy jest np ksiązka Czysty kod [Clean code]. Mimo najlepszych chęci nie ma sposobu, aby przez opisowość [tutaj nie tylko moim zdaniem nadmiarową] kod stał się w 100% procentach samodokumentujący. I tak trzeba zajrzeć do źródeł problemu - tutaj treści zadania. Dobrym pomysłem jest nazywanie rzeczy po angielsku ale … Gdy brak pomysłu można użyć nazw [nawet jedno literowych] zaproponowanych przez autora zadania. Sorry, że to wywlokłem, i tak to rozwlekam/wałkuję, ale to twój kolejny tutaj taki kod i powinieneś mieć świadomość o błędach [moim zdaniem]. Poniżej, przykłady, którem nie są może ścisłymi kopiami twoich nazw, ale chodziło mi o pokazanie sensu:
   Więc raczej nie:
   int jakasZmiennaLiczbowaZIloscZapytan [theNumberOfInqueries
   bo sama deklaracja int mówi o deklaracji zmiennej typu int [liczba całkowita] ale np:
   int pytania [queries] lub po prostu int q
   Podobnie nie:
   set <int> SetOfAllNumbersA … ale raczej set <int> A - nawet używając dużej litery, set to po angielsku między innymi zbiór a w języku matematyki też tak się oznacza zbiór.
   Mam nadzieję, że załapałeś co mam na myśli
6. Pętle w liniach 14-33 są jak najbardziej poprawne ale ja bym to widział np tak [drobna kosmetyka]:

while (dni--)
    {
        double srednia {}; /// lub sredna = 0
        cin >> pomiar;
        for (int i {}; i < m; ++i)     /// m == u Ciebie numberOfMeasurementPoints
            srednia += pomiar[i] - '0';
   /*
lub
       for (auto i : pomiar)
            srednia += i - '0';
*/
        srednia /= m;
        ....
        itd

Każdy koder napisze to po swojemu, więc jeszcze inaczej:

while (dni--) {
    int tmp {}; //nie mam pomysłu na dobrą, krótką nazwę - sumaPomiarów?
  for (auto i : pomiar)
            tmp += i - '0';
  // doble srednia = static_cast <double> (tmp) / m;
  ///czy też od razu:
  if ( static_cast <double> (tmp) / m < dopuszczalnego)  .....
  else ...... 

[odzwp]

dzięki za pomoc, użyłem sum prefiksowych i jest AC