Задача

2/6

lower_bound/upper_bound

Теория Нажмите, чтобы прочитать/скрыть

lower_bound и upper_bound - встроенные функции бинарного поиска.

lower_bound - функция, которая за логарифмическое время в отсортированном массиве находит наименьший элемент, который больше заданного значения k или равен ему.
В качестве аргументов принимает границы массива и значение k.
Возвращает итератор на найденный элемент или на конец (невключенный) массива, если такого элемента не существует.
Подробнее можете прочитать в документации.

upper_bound - функция, которая за логарифмическое время в отсортированном массиве находит наименьший элемент, который строго больше заданного значения k.
В качестве аргументов принимает границы массива и значение k.
Возвращает итератор на найденный элемент или на конец (невключенный) массива, если такого элемента не существует.
Подробнее можете прочитать в документации.

Стоит уточнить, что применение данных функций на set или multiset работает не за логарифмическое время по причине отсутствия у вышеупомянутых коллекций random access итераторов.
Однако у этих коллекций есть соответствующие встроенные методы (то есть нужно использовать их "через точку").

Примеры:
  

	vector a = { 0, 1, 3, 5, 7 };
	vector::iterator it;
	
	it = lower_bound(a.begin(), a.end(), 4);
	// *it == 5

	it = lower_bound(a.begin(), a.end(), 5);
	// *it == 5

	it = lower_bound(a.begin(), a.end(), 8);
	// it == a.end()
	
	it = upper_bound(a.begin(), a.end(), 4);
	// *it == 5

	it = upper_bound(a.begin(), a.end(), 5);
	// *it == 7

	it = upper_bound(a.begin(), a.end(), -1);
	// *it == 0


	// путем вычета итераторов можно получить индекс найденного элемента
	int ind = lower_bound(a.begin(), a.end(), 4) - a.begin();
	// ind == 3


	// нужно использовать методы вместо функций для set и аналогичных коллекций

	set s{ 1, 3, 5 };
	set::iterator sit;

	sit = s.lower_bound(3);
	// *sit == 3

	sit = s.upper_bound(3);
	// *sit == 5
 

Задача

Вам дан упорядоченный массив A из n натуральных чисел. 
Необходимо обработать q запросов. Каждый запрос задается двумя параметрами - его типом ti и числом ki.

Описание запросов по его типу:
1) Найдите в A минимальное число, которое не меньше, чем ki.
2) Найдите в A минимальное число, которое строго больше, чем ki.
3) Найдите в A максимальное число, которое не больше, чем ki.
4) Найдите в A максимальное число, которое строго меньше, чем ki.

Для каждого запроса сообщите найденное число или -1, если такого не существует.

Входные данные:
В первой строке задано число n (1 <= n <= 105) - количество элементов массива A.
Во второй строке задано n натуральных чисел Ai (1 <= Ai <= 109) - сами элементы массива. При этом для всех i < n выполнено Ai <= Ai+1.
В третьей строке задано число q (1 <= q <= 105) - количество запросов.
В следующих q строках дано по два числа - ti (1 <= ti <= 4) и ki (1 <= ki <= 109).

Выходные данные:
Выведите q строк, в i-й одно число - ответ на i-ый запрос.

Примеры:
 
Входные данные Выходные данные
4
3 5 5 7
4
1 5
2 7
3 2
4 4		 5
-1
-1
3


time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Вставьте недостающие фрагменты кода
C++
Напишите программу ниже 
#include <bits/stdc++.h>
using namespace std;
 
int query1(vector<int>& arr, int k) {
	vector<int>::iterator it =     
if (it ==     
)
		return -1;
	return *it;
}

int query2(vector<int>& arr, int k) {
	vector<int>::iterator it =     
if (it ==     
)
		return -1;
	return *it;
}

int query3(vector<int>& arr, int k) {
	vector<int>::iterator it =     
if (it ==     
)
		return -1;
	return *(--it);
}

int query4(vector<int>& arr, int k) {
	vector<int>::iterator it =   
if (it ==     
)
		return -1;
	return *(--it);
}
 
int main()
{
    // ускорение ввода и вывода
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
	cin >> n;

	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int q;
	cin >> q;

	while (q--) {
		int type, k;
		cin >> type >> k;

		if (type == 1)
			cout << query1(arr, k) << endl;
		if (type == 2)
			cout << query2(arr, k) << endl;
		if (type == 3)
			cout << query3(arr, k) << endl;
		if (type == 4)
			cout << query4(arr, k) << endl;
	}
	
	return 0;
}

     

Результат проверки программы 

Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!