ऊँचाई वाली कतार (Height Queue)
आपको
n लोगों की एक कतार दी गई है, जिसमें प्रत्येक व्यक्ति की ऊँचाई एक धनात्मक पूर्णांक के रूप में दी गई है। आपको q क्वेरी (queries) संसाधित करनी हैं, जिनमें से प्रत्येक निम्न दो प्रकारों में से एक है:- Print Shorter People: कतार के सबसे सामने से उन सभी लोगों को हटाएँ और उनकी ऊँचाई प्रिंट करें, जिनकी ऊँचाई
dसे कम या बराबर है, और यह क्रम उनके हटने के क्रम के अनुरूप होना चाहिए।
- Add Person: लंबाई
dवाले एक व्यक्ति को कतार के अंत में जोड़ें।
इन क्वेरी को कुशलतापूर्वक संसाधित करने के लिए एक प्रोग्राम लिखें।
इनपुट (Input)
इनपुट की पहली पंक्ति में दो पूर्णांक
n और q होते हैं, जो क्रमशः प्रारंभिक कतार में लोगों की संख्या और क्वेरी की संख्या दर्शाते हैं (1 ≤ n, q ≤ 100 000)।दूसरी पंक्ति में
n पूर्णांक होते हैं, जहाँ कतार में i-वें व्यक्ति की ऊँचाई को दर्शाता है (1 ≤ ≤ )।अगली
q पंक्तियों में से प्रत्येक पंक्ति एक क्वेरी का प्रतिनिधित्व करती है:pop xयदि यह क्वेरी प्रकार 1 की है, जहाँxस्वीकार्य अधिकतम ऊँचाई है (1 ≤ x ≤ )।
add xयदि यह क्वेरी प्रकार 2 की है, जहाँxउस व्यक्ति की ऊँचाई है जिसे कतार के अंत में जोड़ा जाता है (1 ≤ x ≤ )।
आउटपुट (Output)
प्रकार 1 की प्रत्येक क्वेरी के लिए, हटाए गए लोगों की ऊँचाईयों को उनके पॉप होने के क्रम में, स्पेस से अलग करके एक अलग पंक्ति में प्रिंट करें।
इनपुट (Input) | आउटपुट (Output) |
5 6
5 3 8 7 10
pop 5
add 4
pop 9
add 9
pop 2
pop 11 | 5 3
8 7
10 4 9
|
स्पष्टीकरण (Explanation)
शुरुआती कतार में पाँच लोग मौजूद हैं, जिनकी ऊँचाई क्रमश: 5, 3, 8, 7, और 10 है। निम्न छः क्वेरी इस प्रकार हैं:
- pop 5: कतार में सबसे आगे के दो लोगों (5 और 3) की ऊँचाई 5 से कम या बराबर है, इसलिए उन्हें हटाकर क्रम में प्रिंट किया जाता है, जिसका आउटपुट "5 3" बनता है।
- add 4: ऊँचाई 4 वाला एक व्यक्ति कतार के अंत में जोड़ा जाता है।
- pop 9: अब कतार में सबसे आगे के दो लोग (8 और 7) की ऊँचाई 9 से कम या बराबर है, इसलिए उन्हें हटाकर क्रम में प्रिंट किया जाता है, जिससे आउटपुट "8 7" होता है।
- add 9: ऊँचाई 9 वाला एक व्यक्ति कतार के अंत में जोड़ा जाता है।
- pop 2: इस समय कतार में मौजूद सभी लोगों की ऊँचाई 2 से अधिक है, इसलिए कोई भी नहीं हटाया जाता। आउटपुट खाली पंक्ति रहता है।
- pop 11: अंत में कतार में मौजूद सभी लोगों की ऊँचाई 11 से कम या बराबर है, इसलिए उन्हें क्रमवार हटाकर प्रिंट किया जाता है, जिससे आउटपुट "10 4 9" प्राप्त होता है।
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 10 MB