Przekroczenie limitu czasu

0

Witam, mógłby mi ktoś pomoc znaleźć błąd w kodzie? Ogólnie działa, ale czasem przekroczony jest limit czasu.

Zadanie:
Fizyk-stażysta Bajtazar śledzi działanie Wielkiego Bajtockiego Akceleratora Cząstek. W akceleratorze porusza się duża liczba cząstek o różnych prędkościach (dodatnich albo ujemnych, w zależności od kierunku ruchu). Zadaniem jest mierzenie tych właśnie prędkości. Bajtazar wykrył n cząstek i zmierzył ich prędkości. Z braku lepszych zajęć ustawił wszystkie wyniki pomiarów w kolejności niemalejącej. Opracowanie wyników wymaga jednak odpowiedzi na kilka pytań postaci
„dla zadanej prędkości, ile jest cząstek, które poruszały się z tą właśnie prędkością?” Pomóż mu znaleźć odpowiedzi i zakończyć staż z pozytywną oceną!
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita n (1≤n≤10^5) oznaczająca liczbę cząstek. W drugim wierszu znajduje się n liczb całkowitych o wartości bezwzględnej nie przekraczającej 10^9, oddzielonych spacjami — są to kolejne prędkości cząstek, uporządkowane niemalejąco. W trzecim wierszu znajduje się liczba całkowita q (1≤q≤10^6) oznaczająca liczbę zapytań, które ciekawią Bajtazara. Kolejnych q wierszy zawiera po jednej liczbie całkowitej, której wartość bezwzględna jest nie większa niż 10^ 9– są to prędkości, o które pyta Bajtazar.
Wyjście
Na wyjście wypisz dokładnie q wierszy. Wiersze te powinny zawierać odpowiedzi na kolejne pytania – odpowiedzią jest ilość wystąpień podanej liczby wśród odczytów.
Przykład
Dla danych wejściowych:
5
1 1 2 4 5
3
1
2
3
poprawnym wynikiem jest:
2
1
0

Mój kod:

#include <iostream>
using namespace std;
long long const MAX = 100000;
long long const MAXP = 1000000;
int main()
{
    long long n, T[MAX], q, P[MAXP], sr, k, pie;
    int p;
    cin >> n;
    for (int i = 0; i <= n - 1; i++)
        cin >> T[i];
    cin >> q;
    for (int i = 0; i <= q - 1; i++)
    {
        cin >> P[i];
        p = 0;
        k = n - 1;
        while (p < k)
        {
            sr = (p + k) / 2;
            if (T[sr] >= P[i])
                k = sr;
            else
                p = sr + 1;
        }
        pie = p;
        p = 0;
        k = n - 1;
        while (p < k)
        {
            sr = (p + k + 1) / 2;
            if (T[sr] <= P[i])
                p = sr;
            else
                k = sr - 1;
        }
        if (T[k] == P[i])
            cout << k - pie + 1 << endl;
        else
            cout << 0 << endl;
    }

    return 0;
}
0

Posortuj sobie te dane, użyj lower_bound i upper_bound i złożoność spadnie z O(q·n) do O(q·log2n)

PS: poprawiłem formatowanie. Na przyszłość staraj się sam tworzyć choć trochę czytelny kod.

1

Nie ma błędu (oczywistego), po prostu algorytm jest za wolny. Nie możesz dla każdego zapytania zrobić przeszukiwania całego zbioru, nawet jeśli to wyszukiwanie binarne.
Na oko to wczytaj wszystkie zapytania, posortuj (ale nadal trzymaj pierwotną kolejność), potem przeleć po wszystkich cząstkach i aktualizuj odpowiednie zapytanie na podstawie prędkości cząstki.

1

Ja bym tu zrobił zwykłe zliczanie z użyciem unordered_map. Masz wtedy średni czas O(1) na wyszukiwanie i O(n) na budowę mapy, wiec sumarycznie O(n) zamiast O(nlogn) jak teraz. A i kod sie skróci do 3 linijek... ;]

1

Powiem tak: to jest jedno z tych niedopracowanych zadań ze SPOJ-a, gdzie najbardziej wąskim gardłem są operacje IO.
Twój kod nie przechodzi, bo nie tylko nie wykorzystuje optymalizacji IO, ale robi często flush (endl to robi) na wyjściu co daje dużą karę do wydajności.
Popraw tak:

…
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
…
    // zastąp każde "endl" zwykłym znakiem końca linii '\n'
…
    cout << flush;
    return 0;
}

unordered_map też powinno poprawić wydajność.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0