Problem

2/6

کران_پایین/کران_بالا

Theory Click to read/hide

low_bound و upper_bound توابع جستجوی باینری داخلی هستند.

low_bound - تابعی که در زمان لگاریتمی کوچکترین عنصر را در یک آرایه مرتب شده پیدا می کند که بزرگتر یا مساوی با مقدار داده شده k است.
مرزهای آرایه و مقدار k را به عنوان آرگومان می گیرد.
اگر چنین عنصری وجود نداشته باشد، یک تکرارکننده را به عنصر پیدا شده برمی‌گرداند یا به انتهای آرایه (شامل نمی‌شود).
می‌توانید اطلاعات بیشتری را در اسناد بخوانید.

upper_bound - تابعی است که در زمان لگاریتمی در یک آرایه مرتب شده کوچکترین عنصر را پیدا می کند که به شدت بزرگتر از مقدار داده شده k است.
مرزهای آرایه و مقدار k را به عنوان آرگومان می گیرد.
اگر چنین عنصری وجود نداشته باشد، یک تکرارکننده را به عنصر پیدا شده برمی‌گرداند یا به انتهای آرایه (شامل نمی‌شود).
می‌توانید اطلاعات بیشتری را در اسناد بخوانید.

شایان ذکر است که استفاده از این توابع در یک مجموعه یا چند مجموعه در زمان لگاریتمی به دلیل عدم وجود تکرارکننده در مجموعه‌های دسترسی تصادفی فوق کار نمی‌کند.
با این حال، این مجموعه ها دارای روش های داخلی متناظر هستند (یعنی باید از آنها "از طریق یک نقطه" استفاده کنید).

مثال‌ها:
  بردار a = { 0, 1, 3, 5, 7 }; vector::iterator it; it = low_bound(a.begin(), a.end(), 4); // *it == 5 it = low_bound(a.begin(), a.end(), 5); // *it == 5 it = low_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 // با کم کردن تکرار کننده ها، می توانید شاخص عنصر پیدا شده را بدست آورید int ind = low_bound(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // نیاز به استفاده از متدها به جای توابع برای مجموعه ها و مجموعه های مشابه است set s{ 1, 3, 5 }; set::iterator sit; sit = s.lower_bound(3); // *نشین == 3 sit = s.upper_bound(3); // *نشین == 5  

Problem

یک آرایه مرتب A از n عدد طبیعی به شما داده می شود. 
درخواست های q باید پردازش شوند. به هر پرس و جو دو پارامتر داده می شود - نوع آن ti و عدد ki.

شرح پرس و جوها بر اساس نوع آنها:
1) در A حداقل عددی را پیدا کنید که کمتر از ki نباشد.
2) حداقل عددی را در A بیابید که به شدت بزرگتر از ki باشد.
3) در A حداکثر عددی را بیابید که از ki بزرگتر نباشد.
4) حداکثر عددی را در A بیابید که به شدت کمتر از ki باشد.

برای هر پرس و جو، عدد یافت شده را گزارش کنید، یا -1 اگر وجود ندارد.

ورودی:
خط اول شامل عدد n است (1 <= n <= 105) - تعداد عناصر آرایه A.
خط دوم حاوی n عدد طبیعی Ai است (1 <= Ai <= 109) - خود عناصر آرایه. علاوه بر این، برای همه من < n انجام شد Ai <= Ai+1.
خط سوم شامل عدد q (1 <= q <= 105) - تعداد درخواست‌ها.
خطوط q بعدی هر کدام شامل دو عدد هستند - ti (1 <= ti <= 4) و ki (1 < ;= ki <= 109).

خروجی:
خطوط q را چاپ کنید، i-th one number - پاسخ به i-امین پرس و جو.

مثال:
  <بدن>
ورودی خروجی
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!