Masala #BBSYL56PSV
Yuqori medianli kesmalar
Uzunligi \(n\) bo'lgan \(a_1,a_2,\ldots,a_n\) massiv berilgan.
Uzunligi \(m\) bo'lgan kesmaning yuqori medianasi deb, shu kesma elementlari o'sish tartibida saralangandan keyin \(\left\lfloor \frac{m}{2} \right\rfloor+1\)-o'rinda turgan elementga aytiladi.
Siz massivdan kamida \(k\) ta juft-jufti bilan kesishmaydigan kesma tanlashingiz kerak. Har bir tanlangan kesmaning uzunligi kamida \(L\), ko'pi bilan \(R\) bo'lishi shart.
Tanlangan kesmalar orasidagi eng kichik yuqori mediana imkon qadar katta bo'lishi kerak. Shu maksimal qiymatni toping.
Agar bunday \(k\) ta kesma tanlashning imkoni bo'lmasa, \(-1\) chiqaring.
Kiruvchi ma'lumotlar:
Birinchi qatorda \(t\) — testlar soni beriladi.
Har bir test quyidagi ko'rinishda beriladi:
Birinchi qatorda to'rtta butun son \(n,k,L,R\) beriladi.
Ikkinchi qatorda \(n\) ta butun son \(a_1,a_2,\ldots,a_n\) beriladi.
Cheklovlar:
\[
1 \le t \le 200
\]
\[
1 \le n \le 2\cdot 10^5
\]
\[
1 \le k \le n,
\quad 1 \le L \le R \le n
\]
\[
1 \le a_i \le 10^9
\]
Barcha testlar bo'yicha \(\sum n \le 2\cdot 10^5\).
Chiquvchi ma'lumotlar:
Har bir test uchun alohida qatorda javobni chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 5 2 2 3 1 5 2 4 3 4 2 2 2 7 1 7 1 3 2 2 2 10 20 30 |
4 7 -1 |
Izoh:
Birinchi testda [5,2] va [4,3] kesmalarini tanlash mumkin.
Ularning yuqori medianalari mos ravishda 5 va 4, shuning uchun javob 4.
Ikkinchi testda [7,1] va [7,1] kesmalarini tanlash mumkin.
Ikkalasining ham yuqori medianasi 7.
Uchinchi testda uzunligi 2 bo'lgan ikkita kesishmaydigan kesma tanlab bo'lmaydi.
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring,
agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin
Telegram kanalimizga obuna bo'ling