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;
}