Найти количество чисел меньше заданного?

Question

[dmitrii2004]

На вход подаются N целых чисел, а также набор из M запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших заданного в запросе числа. Использовать встроенные функции бинарного поиска запрещено.

Входные данные

Первая строка содержит число N — количество элементов в массиве. 1≤N≤250000.
Вторая строка содержит N целых чисел Ai через пробел. −109≤Ai≤109.
Третья строка содержит число M — количество запросов. 1≤M≤250000.
Четвёртая строка содержит M целых чисел Qi через пробел. −109≤Qi≤109.

Выходные данные

Выведите единственную строку с M целыми числами — количествами чисел исходного массива, меньших соответствующего запроса.

Примеры
Ввод
Вывод
5
1 5 3 2 1
2
4 3
Вывод
4 3
Ограничения
Время выполнения: 3 секунды

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	unsigned int n;
	cin >> n;
	int* A = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> A[i];
	}
	sort(A, A + n);
	int m;
	cin >> m;
	int x = m;
	int* B = new int[m];
	for (int i = 0; i < m; i++)
	{
		cin >> B[i];
	}
	int f = 250000;
	int* V = new int[f];
	for (int i = 0; i <m; i++)
	{
		int L = -1;
		int R = n;
		while (R - L > 1)
		{
			m = (R + L) / 2;
			if (A[m] < B[i])
			{
				L = m;
			}
			else
			{
				R = m;
			}
		}
		V[i] = R;
	}
	for (int i = 0; i < x; i++)
	{
		cout << V[i] << " ";
	}
}

Помогите пожалуйста ! Сайт пишет, что программа выдаёт неверный ответ

Comments

[Akina]

Отсортировать A[].
Отсортировать Q[], сохраняя номер исходной позиции.
Пройти по паре массивов двумя указателями, получить нужные данные.
Отсортировать Q[] по номеру исходной позиции.
Отдать результат.

Answer 1

[Alexandroppolus]

массив А надобно отсортировать для бинарного поиска.

if(A[m<i]) нет ли тут какой ошибки?

Answer 2

[Wataru]

Куча ошибок. Вы читаете запросы в массив B и больше нигде не используете. Конструкция A{m<i] вообще удивительна. Массив надо отсортировать.

Comments

[dmitrii2004]

Помогите пожалуйста исправил код, но всё равно программа выдаёт неверный ответ

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	unsigned int n;
	cin >> n;
	int* A = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> A[i];
	}
	sort(A, A + n);
	int m;
	cin >> m;
	int x = m;
	int* B = new int[m];
	for (int i = 0; i < m; i++)
	{
		cin >> B[i];
	}
	int f = 250000;
	int* V = new int[f];
	for (int i = 0; i <m; i++)
	{
		int L = -1;
		int R = n;
		while (R - L > 1)
		{
			m = (R + L) / 2;
			if (A[m] < B[i])
			{
				L = m;
			}
			else
			{
				R = m;
			}
		}
		V[i] = R;
	}
	for (int i = 0; i < x; i++)
	{
		cout << V[i] << " ";
	}
}

[Wataru]

dmitrii2004, Переменная m используется и для количества запросов (граница цикла по i) и внутри бинпоиска. Она в бинпоиске перетирается и цикл внезапно заканчивается.

[dmitrii2004]

Wataru, Спасибо большое!