Problem

2/6

limite_inferior/limite_superior

Theory Click to read/hide

lower_bound e upper_bound são funções de busca binária incorporadas.

lower_bound - uma função que, em tempo logarítmico, encontra o menor elemento em uma matriz classificada que é maior ou igual ao valor dado k.
Toma os limites do array e o valor de k como argumentos.
Retorna um iterador para o elemento encontrado, ou para o final (não incluso) do array se tal elemento não existir.
Você pode ler mais na documentação.

upper_bound - uma função que em tempo logarítmico em uma matriz classificada encontra o menor elemento que é estritamente maior que o valor dado k.
Toma os limites do array e o valor de k como argumentos.
Retorna um iterador para o elemento encontrado, ou para o final (não incluso) do array se tal elemento não existir.
Você pode ler mais na documentação.

Vale esclarecer que o uso dessas funções em um conjunto ou multiconjunto não funciona em tempo logarítmico devido à falta de iteradores nas coleções de acesso aleatório acima.
No entanto, essas coleções têm métodos integrados correspondentes (ou seja, você precisa usá-los "através de um ponto").

Exemplos:
  vetor a = { 0, 1, 3, 5, 7 }; vector::iterator it; it = lower_bound(a.begin(), a.end(), 4); // *isso == 5 it = lower_bound(a.begin(), a.end(), 5); // *isso == 5 it = lower_bound(a.begin(), a.end(), 8); // é == a.end() it = upper_bound(a.begin(), a.end(), 4); // *isso == 5 it = upper_bound(a.begin(), a.end(), 5); // *isso == 7 it = upper_bound(a.begin(), a.end(), -1); // *isso == 0 // subtraindo iteradores, você pode obter o índice do elemento encontrado int ind = lower_bound(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // precisa usar métodos em vez de funções para conjuntos e coleções semelhantes set s{ 1, 3, 5 }; set::iterator sit; sentar = s.lower_bound(3); // *senta == 3 senta = s.upper_bound(3); // *senta == 5  

Problem

Você recebe uma matriz ordenada A de n números naturais. 
Existem q solicitações a serem processadas. Cada consulta recebe dois parâmetros - seu tipo ti e o número ki.

Descrição das consultas por tipo:
1) Encontre em A o número mínimo que não seja menor que ki.
2) Encontre o número mínimo em A que é estritamente maior que ki.
3) Encontre em A o número máximo que não seja maior que ki.
4) Encontre o número máximo em A que é estritamente menor que ki.

Para cada consulta, informe o número encontrado ou -1 se não existir.

Entrada:
A primeira linha contém o número n (1 <= n <= 105) - o número de elementos do array A.
A segunda linha contém n números naturais Ai (1 <= Ai <= 109) - os próprios elementos da matriz. Além disso, para todo i < n concluído Ai <= Ai+1.
A terceira linha contém o número q (1 <= q <= 105) - o número de solicitações.
As próximas q linhas contêm dois números cada - ti (1 <= ti <= 4) e ki (1 < ;= ki <= 109).

Saída:
Imprima q linhas, i-ésimo um número - a resposta para a i-ésima consulta.

Exemplos:
 
Entrada Saída
4
3 5 5 7
4
15
27
3 2
4 4		 5
-1
-1
3

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#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;
}

     

Program check result

To check the solution of the problem, you need to register or log in!