Masala #R110B

Xotira 65 MB Vaqt 1000 ms Qiyinchiligi 16 %

#Ochko'z algoritm

#Tartiblash

Panellar

Sizga \(n\) ta panel berilgan. Har bir panel to'g'ri to'rtburchak shaklida bo'lib, ularning eni va bo'yi yig'indisi \(B\) ga teng. Panellar chapdan o'ngga ketma-ket joylashtirilgan. Sizga har bir panelning hozirgi balandligi \(a_i\) beriladi. Istalgan panellarni 90 gradus o'ngga aylantirishingiz mumkin. Agar balandligi \(a_i\) bo'lgan panel aylantirilsa, uning yangi balandligi bu uning eni bo'ladi. Ba'zi panellarni aylantirish orqali panellarning balandliklarini chapdan o'ngga kamaymaydigan tartibga keltirish mumkinmi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t\) — testlar soni beriladi. Har bir test uchun birinchi qatorda ikkita butun son \(n\) va \(B\) beriladi. Ikkinchi qatorda \(n\) ta butun son \(a_1,a_2,\ldots,a_n\) beriladi. Cheklovlar:

\[1 \le t \le 1000\] \[1 \le n \le 2 \cdot 10^5\] \[2 \le B \le 10^9\] \[1 \le a_i < B\]

Bitta testcase ichidagi barcha testlar bo'yicha:

\[\sum n \le 2 \cdot 10^5\]

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda `YES`, agar kerakli tartibga erishish mumkin bo'lsa, aks holda `NO` chiqaring. Javobni istalgan registrda chiqarish mumkin.

Misollar

#	input.txt	output.txt
1	5 3 10 8 3 6 4 10 7 8 6 2 5 12 5 7 6 8 4 1 2 1 4 9 6 5 7 4	YES NO YES YES NO

Izoh:

Birinchi testda panellar balandliklarini \(2,3,4\) qilib tanlash mumkin. Ikkinchi testda hech qanday aylantirishlar orqali balandliklarni kamaymaydigan tartibga keltirib bo'lmaydi.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin