Автор: | Жюри зимних сборов 2009 | Ограничение времени: | 30 сек | |
Входной файл: | dynarray.in | Ограничение памяти: | 512 Мб | |
Выходной файл: | dynarray.out | |||
Максимальный балл: | 100 |
Требуется реализовать структуру данных, которая представляет из себя динамический массив, поддерживающий следующие операции:
Элементы массива нумеруются с единицы.
В первой строке находятся два натуральных числа n и m — начальное количество элементов в массиве и количество операций (1≤n≤200000, 1≤m≤200000). Во второй строке находится n целых чисел a1, a2, …, an — элементы исходного массива (0≤ai≤106). Следующие m строк содержат описания операций в формате "1 u p" (u≥1, u не превосходит текущего размера массива, 0≤p≤106), "2 u p" (u≥0, u не превосходит текущего размера массива, 0≤p≤106) или "3 u v p" (1≤u≤v, v не превосходит текущего размера массива, 0≤p≤106).
В выходном файле должны находиться ответы на запросы — по одному в строке.
№ | Входной файл (dynarray.in ) |
Выходной файл (dynarray.out ) |
---|---|---|
1 |
|
|