মান লিজিয়ে, একটি খালি সিকোয়েন্স এবং n টি কুয়েরি দেওয়া আছে जिन्हें প্রসেস করতে হবে। কুয়েরিগুলো 'queries' অ্যারেতে দেওয়া আছে এবং ফরম্যাট হলো {query, data}। কুয়েরি তিন ধরনের হতে পারে:
query = 1: সরবরাহকৃত data সিকোয়েন্সের শেষে যোগ করুন।
query = 2: সিকোয়েন্সের প্রথম উপাদান প্রিন্ট করুন। তারপর সেই উপাদানটি মুছে ফেলুন।
query = 3: সিকোয়েন্সটিকে আরোহী ক্রমে সোর্ট করুন।
লক্ষ্য করুন, query type 2 এবং 3-র জন্য data সবসময় ০।
যেমন, ইনপুট হলে n = 9, queries = {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}}, তবে আউটপুট হবে 5 এবং 1।
প্রতিটি কুয়েরির পর সিকোয়েন্স নিচের মতো:
- 1: {5}
- 2: {5, 4}
- 3: {5, 4, 3}
- 4: {5, 4, 3, 2}
- 5: {5, 4, 3, 2, 1}
- 6: {4, 3, 2, 1}, প্রিন্ট ৫।
- 7: {1, 2, 3, 4}
- 8: {2, 3, 4}, প্রিন্ট ১।
- 9: {2, 3, 4}
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
priq প্রায়োরিটি কিউ সংজ্ঞায়িত করুন q কিউ সংজ্ঞায়িত করুন i := 0 থেকে n-1 পর্যন্ত: operation := queries[i]-র ১ম মান if operation == 1, তবে: x := queries[i]-র ২য় মান q-তে x যোগ করুন অন্যথায় যদি operation == 2, তবে: if priq খালি, তবে: q-র প্রথম উপাদান প্রিন্ট করুন q-র প্রথম উপাদান মুছুন অন্যথায়: -(priq-র টপ উপাদান) প্রিন্ট করুন priq-র টপ উপাদান মুছুন অন্যথায় যদি operation == 3, তবে: while (q খালি নয়): -q-র প্রথম উপাদান priq-তে যোগ করুন এবং সোর্ট করুন q-র উপাদান মুছুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; void solve(int n, vector<pair<int, int>> queries){ priority_queue<int> priq; queue<int> q; for(int i = 0; i < n; i++) { int operation = queries[i].first; if(operation == 1) { int x; x = queries[i].second; q.push(x); } else if(operation == 2) { if(priq.empty()) { cout << q.front() << endl; q.pop(); } else { cout << -priq.top() << endl; priq.pop(); } } else if(operation == 3) { while(!q.empty()) { priq.push(-q.front()); q.pop(); } } } } int main() { int n = 9; vector<pair<int, int>> queries = {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}}; solve(n, queries); return 0; } ইনপুট
9, {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}} আউটপুট
5 1
