Трохи складніші запити
Обмеження: 2 сек., 256 МіБ
Задано масив \(a\) із \(n\) натуральних чисел. Потрібно відповісти на \(m\) запитів, кожен з яких одного із двох типів:
знайти розмір найбільшого префіксу масиву, сума чисел в якому не перевищує \(x\),
додати натуральне число \(d\) до \(i\)-го елементу.
Вхідні дані
У першому рядку задано два цілих числа \(n\) і \(m\) — розмір масиву та кількість запитів відповідно.
У другому рядку задано \(n\) цілих чисел \(a_i\) — елементи масиву.
У наступних \(m\) рядках задано запити, по одному у рядку, у такому форматі:
1 x
— запит першого типу,2 i d
— запит другого типу.
Вихідні дані
Для кожного запиту першого типу виведіть, в окремому рядку, розмір найбільшого префіксу, сума чисел на якому не перевищує \(x\).
Обмеження
\(1 \le n, m \le 10^5\).
\(1 \le a_i, d \le 10^3\).
\(1 \le i \le n\).
\(1 \le x \le 10^9\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
8 3 1 4 2 1 7 3 5 2 1 15 2 4 4 1 13 | 5 4 |
Примітки
Зауважте, що розмір префіксу може бути рівний 0
.
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|