Problem

2/6

Theory Click to read/hide

nieder_bound und top_bound - integrierte binäre Suchfunktionen.

nieder_bound ist eine Funktion, die für die logarithmische Zeit in der Klebemasse das mindestens Element findet, das größer oder gleich dem zugeordneten Wert k ist.
Als Argumente werden die Grenzen von Masse und Bedeutung k akzeptiert.
Er kehrt den Terator an das gefundene Element oder an das Ende der Masse zurück, wenn kein solches Element vorhanden ist.
Sie können die Details lesen. Dokumentation♪

top_bound ist eine Funktion, die für die logarithmische Zeit in der Klebemasse das kleinste Element findet, das mehr ist als der zugeordnete Wert k.
Als Argumente werden die Grenzen von Masse und Bedeutung k akzeptiert.
Er kehrt den Terator an das gefundene Element oder an das Ende der Masse zurück, wenn kein solches Element vorhanden ist.
Sie können die Details lesen. Dokumentation♪

Es ist klarzustellen, dass die Verwendung dieser Funktionen auf Set oder Multiset aufgrund des Fehlens eines zufälligen Zugriffs durch die oben genannten Sammlungen nicht für die logarithmische Zeit funktioniert.
Diese Sammlungen haben jedoch entsprechende integrierte Methoden (d.h. ihre Cut-offs verwenden).

Beispiele:

Vektor a = {0, 1, 3, 5, 7};
Vektor:

es = nieder_bound(a.begin(), a.end(), 4);
♪

es = nieder_bound(a.begin(), a.end(), 5);
♪

es = nieder_bound(a.begin(), a.end(), 8);
// it == sync, korrigiert von elderman == @elder_man

es = top_bound(a.begin(), a.end(), 4);
♪

es = top_bound(a.begin(), a.end(), 5);
♪

es = top_bound(a.begin(), a.end(), -1);
♪


/ durch Abzug der Iteratoren kann ein Index des gefundenen Elements erhalten werden
int ind = nieder_bound(a.begin(), a.end(), 4) - a.begin();
/ ind == sync, berichtigt von elderman == @elder_man


/ Verwenden Sie Methoden, um Funktionen für Set und ähnliche Sammlungen zu ersetzen

Menge s{ 1, 3, 5};
Menge:

Sitz = s.lower_bound(3);
♪

Sitz = s.upper_bound(3);
♪

Problem

Sie erhalten eine ordentliche A von n natürlichen Zahlen.
q Anfragen müssen bearbeitet werden. Jeder Antrag ist durch zwei Parameter, dessen Typ tI Anzahl kI♪

Beschreibung der Anträge nach Typ:
(1) In einer Mindestzahl von mindestens kI♪
(2) Finde eine Mindestnummer in A, die mehr als k istI♪
(3) Finden Sie eine maximale Anzahl in A, die nicht mehr als k istI♪
(4) Finden Sie eine maximale Anzahl in A, die streng unter k liegtI♪

Bitte geben Sie für jede Anfrage die Nummer oder -1 an, wenn sie nicht vorhanden ist.

Eingabe:
In der ersten Zeile wurde die Anzahl n (1 PO=n PO= 10) angefordert.5.) - Anzahl der Elemente von A.
In der zweiten Zeile n natürliche Zahlen AI 1 Zug = AI · 10ANHANG- Die Elemente des Körpers selbst. Zur gleichen Zeit, für alle i PAN n abgeschlossen AI Ài+1♪
In der dritten Zeile wurde die Anzahl von q (1 Kanal = q ΔP = 10) aufgetragen.5.Anzahl der Anträge.
In den folgenden q Zeilen, zwei Zahlen - tI (1 Kanal) tI und kI 1 Zug = kI · 10ANHANG)

Ausgangsdaten:
Nehmen Sie die Q-Linie aus, eine Ziffer in der i.

Beispiele:
EingangsdatenAusgangsdaten
ANHANG
3 5 7
ANHANG
Artikel 1
Artikel 7
Artikel 2
ANHANG		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!