Problem

2/6

alt_sınır/üst_sınır

Theory Click to read/hide

lower_bound ve Upper_bound yerleşik ikili arama işlevleridir.

lower_bound - logaritmik zamanda, sıralanmış bir dizideki verilen k değerinden büyük veya ona eşit olan en küçük öğeyi bulan bir işlev.
Argüman olarak dizinin sınırlarını ve k değerini alır.
Bulunan öğeye veya böyle bir öğe yoksa dizinin sonuna (dahil değildir) bir yineleyici döndürür.
belgelerde daha fazla bilgi edinebilirsiniz.

Upper_bound - sıralanmış bir dizide logaritmik zamanda verilen k değerinden kesinlikle büyük olan en küçük öğeyi bulan bir işlev.
Argüman olarak dizinin sınırlarını ve k değerini alır.
Bulunan öğeye veya böyle bir öğe yoksa dizinin sonuna (dahil değildir) bir yineleyici döndürür.
belgelerde daha fazla bilgi edinebilirsiniz.

Yukarıdaki rasgele erişim koleksiyonlarında yineleyicilerin olmaması nedeniyle bu işlevlerin bir küme veya çoklu küme üzerinde kullanımının logaritmik zamanda çalışmadığını açıklığa kavuşturmakta fayda var.
Ancak, bu koleksiyonların karşılık gelen yerleşik yöntemleri vardır (yani, bunları "nokta aracılığıyla" kullanmanız gerekir).

Örnekler:
  vektör a = { 0, 1, 3, 5, 7 }; vektör::iterator it; o = lower_bound(a.begin(), a.end(), 4); // *it == 5 o = lower_bound(a.begin(), a.end(), 5); // *it == 5 o = lower_bound(a.begin(), a.end(), 8); // o == a.end() o = üst_sınır(a.begin(), a.end(), 4); // *it == 5 o = üst_sınır(a.begin(), a.end(), 5); // *it == 7 o = üst_sınır(a.begin(), a.end(), -1); // *it == 0 // yineleyicileri çıkararak bulunan öğenin dizinini elde edebilirsiniz int ind = lower_bound(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // set ve benzeri koleksiyonlar için fonksiyonlar yerine metodların kullanılması gerekiyor set s{ 1, 3, 5 }; set::yineleyici sit; otur = s.lower_bound(3); // *otur == 3 otur = s.upper_bound(3); // *otur == 5  

Problem

Size n doğal sayıdan oluşan sıralı bir A dizisi verildi. 
İşlenecek q istek var. Her sorguya iki parametre verilir - türü ti ve ki sayısı.

Türlerine göre sorguların açıklaması:
1) A'da ki'den küçük olmayan minimum sayıyı bulun.
2) A'da ki'den kesinlikle büyük olan minimum sayıyı bulun.
3) A'da ki'den büyük olmayan maksimum sayıyı bulun.
4) A'da kesinlikle ki'den küçük olan maksimum sayıyı bulun.

Her sorgu için, bulunan sayıyı veya yoksa -1'i bildirin.

Giriş:
İlk satır n sayısını içerir (1 <= n <= 105) - A dizisinin eleman sayısı.
İkinci satır n doğal sayı Ai (1 <= Ai <= 109) içerir - dizi öğelerinin kendileri. Ayrıca, tüm i < n yapıldı Ai <= Ai+1.
Üçüncü satır q (1 <= q <= 105) sayısını içerir - isteklerin sayısı.
Sonraki q satırlarının her biri iki sayı içerir - ti (1 <= ti <= 4) ve ki (1 < ;= ki <= 109).

Çıktı:
q satırlarını yazdır, i'inci bir sayı - i'inci sorgunun yanıtı.

Örnekler:
 

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++
Giriş Çıktı
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!