10241: Достатня сума на відрізку


Відправити розв'язок

Бали: 100 (partial)
Time limit: 0.3s
Memory limit: 64M

Author:
Problem type
Allowed languages
Brain****, C, C++, Java, Pascal, Python, v8js

Реалізуйте дерево відрізків для знаходження накоротшого префіксу відрізку з заданою сумою.

Формат вхідних даних

В першому рядку ціле число \(N\), кількість елементів масиву (\(1 \le N \le 10^5\)).
В другому рядку елементи масиву. (\(0 \le Ai \le 10^5\))
В третьому рядку вводиться число \(P\) - кількість запитів (\(1 \le P \le 3*10^4\))
В кожному з наступних \(P\) рядків міститься по три числа - номера лівого і правого елементів відрізка масиву, та сума яку необхідно набрати на префіксі відрізка.

Формат вихідних даних

Для кожного запиту виведіть через пробіл - найменшу кількість елементів на префіксі запиту, які дадуть потрібну суму. Якщо таку суму на відрізку отримати неможливо, виведіть -1

Приклад вхідних даних

5
2 2 2 1 5 
4
2 3 3
2 5 6
3 4 7
3 5 0

Приклад вихідних даних

2 4 -1 0

Пояснення до прикладу

В першому запиті на відрізку [2,3] необхідно набрати суму 3, для цього необхідно буде взяти обидва елемента 2+2=4 В другому запиті на відрізку [2,5] необхідно набрати суму 6, для цього необхідно буде взяти три елемента 2+1+5=8 В третьому запиті на відрізку [3,4] необхідно набрати суму 7, а це неможливо, бо сума всіх елеменітв відрізка 2+1=3 менша за 7 В четвертому запиті на відрізку [3,7] необхідно набрати суму 0, для цього потрібно - чисел


Коментарі

Ще немає коментарів.