Problem

2/6

limite_inferiore/limite_superiore

Theory Click to read/hide

lower_bound e upper_bound sono funzioni di ricerca binaria integrate.

lower_bound - una funzione che, in tempo logaritmico, trova l'elemento più piccolo in un array ordinato maggiore o uguale al valore dato k.
Prende i limiti dell'array e il valore di k come argomenti.
Restituisce un iteratore all'elemento trovato o alla fine (non inclusa) dell'array se tale elemento non esiste.
Puoi leggere ulteriori informazioni nella documentazione.

upper_bound - una funzione che in tempo logaritmico in un array ordinato trova l'elemento più piccolo strettamente maggiore del valore dato k.
Prende i limiti dell'array e il valore di k come argomenti.
Restituisce un iteratore all'elemento trovato o alla fine (non inclusa) dell'array se tale elemento non esiste.
Puoi leggere ulteriori informazioni nella documentazione.

Vale la pena chiarire che l'uso di queste funzioni su un set o multiset non funziona in tempo logaritmico a causa della mancanza di iteratori nelle raccolte ad accesso casuale di cui sopra.
Tuttavia, queste raccolte hanno metodi incorporati corrispondenti (ovvero, è necessario utilizzarle "attraverso un punto").

Esempi:
  vettore a = { 0, 1, 3, 5, 7 }; vector::iteratore 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 // sottraendo gli iteratori, puoi ottenere l'indice dell'elemento trovato int ind = lower_bound(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // è necessario utilizzare metodi anziché funzioni per raccolte di insiemi e simili set s{ 1, 3, 5 }; set::iterator sit; sit = s.lower_bound(3); // *seduto == 3 sit = s.upper_bound(3); // *seduto == 5  

Problem

Ti viene fornito un array ordinato A di n numeri naturali. 
Ci sono q richieste da elaborare. A ciascuna query vengono assegnati due parametri: il tipo ti e il numero ki.

Descrizione delle query in base al tipo:
1) Trova in A il numero minimo che non sia minore di ki.
2) Trova il numero minimo in A strettamente maggiore di ki.
3) Trova in A il numero massimo che non sia maggiore di ki.
4) Trova il numero massimo in A che è strettamente minore di ki.

Per ogni query, riporta il numero trovato o -1 se non esiste.

Inserimento:
La prima riga contiene il numero n (1 <= n <= 105) - il numero di elementi dell'array A.
La seconda riga contiene n numeri naturali Ai (1 <= Ai <= 109) - gli elementi dell'array stessi. Inoltre, per tutti i < n fatto LAi <= LAi+1.
La terza riga contiene il numero q (1 <= q <= 105) - il numero di richieste.
Le q righe successive contengono ciascuna due numeri - ti (1 <= ti <= 4) e ki (1 < ;= ki <= 109).

Uscita:
Stampa q righe, i-esimo numero - la risposta all'i-esimo interrogazione.

Esempi:
 
Input Uscita
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!