Interesting. I needed a similar data structure once and ended up using linked list (but it had exactly $VERTICAL_RESOLUTION big elements so the memory cost for poitners was negligible, and the most common operation was moving all elements left(up) or right(down) and linked list is hard to beat at that).