  Consider a variant of Tetris played on a board of width $w$ and infinite
height, where the pieces are axis-aligned rectangles of arbitrary integer
dimensions, the pieces can only be moved before letting them drop, and a row
does not disappear once it is full. Suppose we want to follow a greedy
strategy: let each rectangle fall where it will end up the lowest given the
current state of the board. To do so, we want a data structure which can always
suggest a greedy move. In other words, we want a data structure which maintains
a set of $O(n)$ rectangles, supports queries which return where to drop the
rectangle, and updates which insert a rectangle dropped at a certain position
and return the height of the highest point in the updated set of rectangles. We
show via a reduction to the Multiphase problem [P\u{a}tra\c{s}cu, 2010] that on
a board of width $w=\Theta(n)$, if the OMv conjecture [Henzinger et al., 2015]
is true, then both operations cannot be supported in time $O(n^{1/2-\epsilon})$
simultaneously. The reduction also implies polynomial bounds from the 3-SUM
conjecture and the APSP conjecture. On the other hand, we show that there is a
data structure supporting both operations in $O(n^{1/2}\log^{3/2}n)$ time on
boards of width $n^{O(1)}$, matching the lower bound up to a $n^{o(1)}$ factor.
