Бинарный поиск, C. Запросы о количестве не превосходящих элементов

Заданы два массива чисел a и b. Для каждого элемента второго массива b j нужно найти количество элементов в массиве a, которые меньше либо равны b j.

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

В первой строке находятся два целых числа n, m (1 ≤ n, m ≤ 2·10^5) — размеры массивов a и b.

Во второй строке находятся n целых чисел — элементы массива a ( - 10^9 ≤ a_i ≤ 10^9).

В третьей строке находятся m целых чисел — элементы массива b ( - 10^9 ≤ b_j ≤ 10^9).

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

Выведите m чисел, разделенных пробелами: j-е из них равно количеству таких элементов массива a, которые меньше или равны числа b j.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int a[n];
    
    for(int i=0; i < n; i++) {
        cin >> a[i];
    }
    
    sort(a, a + n);
    
    for(int i=0; i < m; i++){
        int x;
        cin >> x;
        
        int f = (lower_bound ( a + 0, a + n, x)-a);
        int j = (upper_bound ( a + 0, a + n, x)-a);
        if(a[j] > x) cout << j << " ";
        else cout << f + 1 << " ";
        
    }
  
    return 0;
 }

Не могу понять где у меня ошибка в коде.Выходить что есть ошибка в тесте 4

У тебя тут j может быть равен n, а размер массива n, обращение к a[n] элементу может вызвать ошибку.

Посмотри тест

4 1
1 2 2 2
2

3 лайка

Почему?

Я проверил и вроде всеравно вышло

4

Использовано: 0 мс, 0 КБ

Ты выходишь за границы массива

Попробуй тест:

4 1
1 1000000000 1000000000 1000000000
1000000000

Ну короче мысль в том что элемента a[n] Не существует, а значит оно обращается в никуда, и там какое то рандомное значение, и если это рандомное значение меньше x то тебе выведет неправильный ответ, увеличь размер массива на 1 и поставь a[n] = 2e9.

1 лайк