Олимпиадный тренинг

Задача . lower_bound/upper_bound


Задача

Темы:
Вам дан упорядоченный массив 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
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6412
Комментарий учителя

Ваш ответ

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

Загруженные файлы
Нет