Masala #G2TXFP86QA

Xotira 128 MB Vaqt 10000 ms Qiyinchiligi 1 %

Weak Point

Siz armiyaning qo‘mondonisiz. Armiyada \(n\) ta askar bor, ular 1 dan n gacha raqamlangan.
Har bir askarning o‘z kuchi mavjud — massiv \(a[1..n]\).

Biror \([l, r]\) oraliqdagi askarlardan guruh tashkil qilinsa, bu guruhning weak point (zaif nuqtasi) quyidagicha aniqlanadi:

Weak point - ushbu oraliqda uchramaydigan eng kichik nomanfiy butun son, ya’ni \(MEX(l, r)\).

Guruhning umumiy kuchi esa quyidagicha hisoblanadi:

\[Power(l, r) = MEX(l, r) \times \sum_{i=l}^{r} a[i]\]

Sizga \(q\) guruh beriladi. Har bir guruh \([l_i, r_i]\) oraliq bilan berilgan.
Sizning vazifangiz — berilgan barcha guruhlar orasida eng kuchli guruhning kuchini aniqlash.

Kiruvchi ma'lumotlar:

Birinchi qatorda Ikkita natural son \(n, q\) - mos ravishda armiyadagi askarlar soni hamda so'rovlar soni beriladi. \((1\le n, q\le 10^5)\)

Ikkinchi qatorda \(n\) ta butun son - askarlarning kuchlari beriladi. \((0\le a[i]\le 10^9)\)

Keyingi qatordan boshlab \(q\) ta qatorda guruhlar kiritiladi. \((1\le l_i \le r_i \le n)\)

Chiquvchi ma'lumotlar:

Yagona qatorda bitta natural son - eng kuchli guruhning kuchini chiqaring.

Misollar

#	input.txt	output.txt
1	5 3 0 1 2 3 4 2 3 1 3 5 5	9

Telegram Facebook

Yechimini yuborish

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