Problem

2/6

límite_inferior/límite_superior

Theory Click to read/hide

lower_bound y upper_bound son funciones de búsqueda binaria integradas.

lower_bound: una función que, en tiempo logarítmico, encuentra el elemento más pequeño en una matriz ordenada que es mayor o igual que el valor dado k.
Toma los límites de la matriz y el valor de k como argumentos.
Devuelve un iterador al elemento encontrado, o al final (no incluido) de la matriz si no existe dicho elemento.
Puede leer más en la documentación.

upper_bound - una función que en tiempo logarítmico en una matriz ordenada encuentra el elemento más pequeño que es estrictamente mayor que el valor k dado.
Toma los límites de la matriz y el valor de k como argumentos.
Devuelve un iterador al elemento encontrado, o al final (no incluido) de la matriz si no existe dicho elemento.
Puede leer más en documentación.

Vale la pena aclarar que el uso de estas funciones en un conjunto o conjunto múltiple no funciona en tiempo logarítmico debido a la falta de iteradores en las colecciones de acceso aleatorio anteriores.
Sin embargo, estas colecciones tienen métodos incorporados correspondientes (es decir, debe usarlos "a través de un punto").

Ejemplos:
  vector a = { 0, 1, 3, 5, 7 }; vector::iterarlo; it = límite_inferior(a.begin(), a.end(), 4); // *es == 5 it = límite_inferior(a.begin(), a.end(), 5); // *es == 5 it = límite_inferior(a.begin(), a.end(), 8); // it == a.end() it = límite_superior(a.begin(), a.end(), 4); // *es == 5 it = límite_superior(a.begin(), a.end(), 5); // *es == 7 it = límite_superior(a.begin(), a.end(), -1); // *es == 0 // al restar los iteradores, puede obtener el índice del elemento encontrado int ind = límite_inferior(a.begin(), a.end(), 4) - a.begin(); // indicador == 3 // necesita usar métodos en lugar de funciones para conjuntos y colecciones similares conjunto s{ 1, 3, 5 }; establecer::iterador sentarse; sentarse = s.lower_bound(3); // *sentarse == 3 sentarse = s.superior_límite(3); // *sentarse == 5  

Problem

Se te da una matriz ordenada A de n números naturales. 
Hay q solicitudes para ser procesadas. Cada consulta recibe dos parámetros: su tipo ti y el número ki.

Descripción de las consultas por su tipo:
1) Encuentra en A el número mínimo que no sea menor que ki.
2) Encuentra el número mínimo en A que es estrictamente mayor que ki.
3) Encuentra en A el número máximo que no sea mayor que ki.
4) Encuentra el número máximo en A que es estrictamente menor que ki.

Para cada consulta, informe el número encontrado, o -1 si no existe ninguno.

Entrada:
La primera línea contiene el número n (1 <= n <= 105) - el número de elementos de la matriz A.
La segunda línea contiene n números naturales Ai (1 <= Ai <= 109) - los propios elementos de la matriz. Además, para todos i < n hecho Ai <= Ai+1.
La tercera línea contiene el número q (1 <= q <= 105) - el número de solicitudes.
Las siguientes q líneas contienen dos números cada una: ti (1 <= ti <= 4) y ki (1 < ;= ki <= 109).

Salida:
Imprima q líneas, i-ésimo número: la respuesta a la i-ésima consulta.

Ejemplos:
 

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++
Entrada Salida
4
3 5 5 7
4
15
27
3 2
4 4		 5
-1
-1
3
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!