Problem

2/6

निचला_बाउंड/ऊपरी_बाउंड

Theory Click to read/hide

लोअर_बाउंड और अपर_बाउंड बिल्ट-इन बाइनरी सर्च फंक्शन हैं।

निचला_बाउंड - एक फ़ंक्शन जो लघुगणकीय समय में, क्रमबद्ध सरणी में सबसे छोटा तत्व पाता है जो दिए गए मान k से अधिक या उसके बराबर होता है।
यह सरणी की सीमा और k के मान को तर्क के रूप में लेता है।
यदि ऐसा कोई तत्व मौजूद नहीं है, तो पाया गया तत्व या सरणी के अंत (शामिल नहीं) के लिए एक पुनरावर्तक लौटाता है।
आप दस्तावेज़ीकरण में अधिक पढ़ सकते हैं।

अपर_बाउंड - एक फ़ंक्शन जो लघुगणकीय समय में एक क्रमबद्ध सरणी में सबसे छोटा तत्व पाता है जो दिए गए मान k से सख्ती से अधिक है।
यह सरणी की सीमा और k के मान को तर्क के रूप में लेता है।
यदि ऐसा कोई तत्व मौजूद नहीं है, तो पाया गया तत्व या सरणी के अंत (शामिल नहीं) के लिए एक पुनरावर्तक लौटाता है।
आप दस्तावेज़ीकरण में अधिक पढ़ सकते हैं।

यह स्पष्ट करने योग्य है कि उपरोक्त रैंडम एक्सेस संग्रह में पुनरावृत्तियों की कमी के कारण सेट या मल्टीसेट पर इन कार्यों का उपयोग लघुगणकीय समय में काम नहीं करता है।
हालाँकि, इन संग्रहों में संबंधित अंतर्निहित विधियाँ हैं (अर्थात, आपको उन्हें "डॉट के माध्यम से" उपयोग करने की आवश्यकता है)।

उदाहरण:
  वेक्टर ए = {0, 1, 3, 5, 7}; वेक्टर::इटरेटर इट; यह = निचला_बाउंड (a.begin (), a.end (), 4); // * यह == 5 यह = निचला_बाउंड (a.begin (), a.end (), 5); // * यह == 5 यह = निचला_बाउंड (a.begin (), a.end (), 8); // यह == a.end () यह = ऊपरी_बाउंड (a.begin (), a.end (), 4); // * यह == 5 यह = ऊपरी_बाउंड (a.begin (), a.end (), 5); // * यह == 7 यह = ऊपरी_बाउंड (a.begin (), a.end (), -1); // * यह == 0 // पुनरावृत्तियों को घटाकर, आप पाए गए तत्व का सूचकांक प्राप्त कर सकते हैं int ind = निचला_बाउंड (a.begin (), a.end (), 4) - a.begin (); // इंडस्ट्रीज़ == 3 // सेट और समान संग्रह के कार्यों के बजाय विधियों का उपयोग करने की आवश्यकता है सेट एस {1, 3, 5}; सेट :: इटरेटर बैठो; बैठो = s.lower_bound (3); // *बैठो == 3 बैठो = s.upper_bound (3); // *बैठो == 5  

Problem

आपको n प्राकृतिक संख्याओं की एक क्रमित सरणी A दी गई है। 
संसाधित करने के लिए 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).

आउटपुट:
क्यू लाइन प्रिंट करें, i-वें एक नंबर - i-वें प्रश्न का उत्तर।

उदाहरण:
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;"> <शरीर> इनपुट आउटपुट 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!