Masala E

Nyuboy CP(Competitive Programming)ga qiziqadi. U hozir bitta masalani ishlayotgan edi. Nyuboy ushbu masalani 2-urinishda hal qildi. Sizga Nyuboyning 1-yechimi beriladi. Siz ushbu masalani ishlay olasizmi?

!!! Nyuboyning 1-yechimidagi yagona muammo Time Limit edi.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int n, q; cin >> n >> q;
	vector <int> a(n + 1);
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	while (q --){
		int l, r, k;
		cin >> l >> r >> k;
		vector <int> b;
		for (int i = l; i <= r; ++ i) b.push_back(a[i]);
		sort(b.begin(), b.end());
		cout << b[k - 1] << '\n';
	}
	return 0;
}

Birinchi qatorda n va q natural sonlari kiritiladi. $(n, q \le 10^5)$

Ikkinchi qatorda n ta natural son kiritiladi. $(1 \le i \le n  ,  a[i] \le 10^5)$

Keyingi q ta qatorning har birida l, r va k natural sonlari kiritiladi.

$(1 \le l \le r \le n,   k \le r - l  + 1)$

Masalaning javobini chop eting.