Problem p03709 (python)

Fixed submission:
from bisect import bisect_left, bisect_right
import fileinput


MODULO = 1000000007
n = 0


# HANDLE INPUT
def handle_input():
    iterator = fileinput.input()
    global n
    n = int(next(iterator))
    takahashis = [None] * n
    for i in xrange(n):
        x, v = next(iterator).split()
        takahashis[i] = (int(x), int(v))
    return takahashis


def build_blocks(takahashis):
    result = [-1] * (n + 1)
    max_velocities = [0] * n
    min_velocities = [MODULO] * (n + 1)
    for i in xrange(n):
        max_velocities[i] = max(max_velocities[i - 1], takahashis[i][1])
    for i in xrange(n-1, -1, -1):
        min_velocities[i] = min(min_velocities[i + 1], takahashis[i][1])
    for i in xrange(n):
        current_velocity = takahashis[i][1]
        block_start = bisect_left(max_velocities, current_velocity)
        block_end = bisect_right(min_velocities, current_velocity) - 1
        result[block_end] = max(result[block_end], block_start)
    return result


def compute_possibilities(blocks):
    possibilities = [1] * (n + 2)
    zeros_end_cursor = -2
    for current_position in xrange(n):
        result = 2 * possibilities[current_position - 1]
        # Remove possibiltiies for (00..)1{.....} sequences.
        while zeros_end_cursor < blocks[current_position] - 1:
            result -= possibilities[zeros_end_cursor]
            zeros_end_cursor += 1
        possibilities[current_position] = result % MODULO
    return possibilities[n - 1]


def main():
    takahashis = handle_input()
    takahashis.sort()
    blocks = build_blocks(takahashis)
    return compute_possibilities(blocks)


if __name__ == '__main__':
    print main()

Buggy submission (verdict: Runtime Error):
from collections import OrderedDict, deque
import heapq
import fileinput

# def file_iterator(file_name):
#     with open(file_name) as f:
#         for line in f:
#             yield line

iterator = fileinput.input()
# iterator = file_iterator('input2.txt')



MAX_VELOCITY = 1000000000
MAX_N = 200000
MODULO =  1000000007


# class Takahashi(object):
#     __slots__ = ['position', 'velocity', 'block_start', 'block_end', 'seen']

#     def __init__(self, position, velocity):
#         self.position = position
#         self.velocity = velocity
#         self.block_start = None
#         self.block_end = None
#         self.seen = False


n = 0
takahashis = []
velocities = []
# maps a block index (0...N-1) to start (or end) of its corresponding block.
block_starts = []
block_ends = []
seen = []
# all stops we take along the way
block_starting_positions = OrderedDict()
block_ending_positions = OrderedDict()
# possibilities[i] indicates the number of possibilities
# from block with indices 0 to i.
possibilities = []


# HANDLE INPUT
def handle_input():
    def read_stuff():    
        global n
        n = int(iterator.next())
        takahashis[:] = [None] * n
        for i in xrange(n):
            x, v = iterator.next().split()
            takahashis[i] = (int(x), int(v))

    def sort_stuff():
        takahashis.sort()

    def define_stuff():
        # maps a block index (0...N-1) to start (or end) of its corresponding block.
        block_starts[:] = [None] * n
        block_ends[:] = [None] * n
        seen[:] = [False] * n
        possibilities[:] = [None] * (n + 1)


    read_stuff()
    sort_stuff()
    define_stuff()


def turn_input_into_blocks():
    def define_stuff_2():
        velocities[:] = ((t[1], i) for i, t in enumerate(takahashis))

    def sort_stuff_2():
        velocities.sort()

    def iterate_stuff_2():
        velocity_cursor = 0
        rightmost_smaller_velocity_index = 0

        for i in xrange(n):
            if seen[i]: continue

            # Determine end of block involving the smallest unseen velocity.
            # Also, get index of rightmost smaller velocity and mark as seen
            first = True
            t = takahashis[i]
            while velocity_cursor < n - 1 and t[1] >= takahashis[velocities[velocity_cursor + 1][1]][1]:
                velocity_cursor += 1
                upcoming_smaller_velocity_index = velocities[velocity_cursor][1]
                seen[upcoming_smaller_velocity_index] = True
                rightmost_smaller_velocity_index = max(
                    rightmost_smaller_velocity_index, upcoming_smaller_velocity_index)
                if first:
                    block_end = rightmost_smaller_velocity_index
                    first = False

            block_starts[i] = i
            block_ends[i] = block_end
            # check if already have a longer block ending at same position
            previous_longer_block = block_ending_positions.get(block_end)
            if previous_longer_block is not None:
                del block_starting_positions[block_starts[previous_longer_block]]
            block_starting_positions[i] = i
            block_ending_positions[block_end] = i

    def return_stuff_2():
        sentinel = [n - 1] if n - 1 not in block_ending_positions else []
        return heapq.merge(block_starting_positions, block_ending_positions, sentinel)

    define_stuff_2()
    sort_stuff_2()
    iterate_stuff_2()
    return return_stuff_2()


def build_stops_iterator(stops):
    current_position = None
    while True:
        next_position = next(stops, None)
        if next_position == current_position:
            next_position = next(stops, None)
        current_position = next_position
        if current_position is not None:
            yield current_position
        else:
            break


def compute_possibilities(stops_iterator):
    possibilities[-1] = 1
    active_blocks = deque()
    current_position = 0
    alpha = 0
    while current_position < n:
        # fast track check
        next_position = next(stops_iterator, None)
        indices_to_move = next_position - current_position
        if indices_to_move > 0:
            # fast track for `indices_to_move` rounds where no block starts or ends.
            k, p = indices_to_move, possibilities[current_position - 1]
            possibilities[current_position - 1 + k] = (
                pow(2, k, MODULO) * p + (pow(2, k, MODULO) - 1) * alpha) % MODULO
            # move forward
            current_position += indices_to_move

        # update active blocks
        has_new_block = current_position in block_starting_positions
        if has_new_block:
            active_blocks.append(current_position)
            alpha += possibilities[current_position - 1]

        # compute result
        result = alpha + (2 * possibilities[current_position - 1] if not has_new_block else 0)
        possibilities[current_position] = result % MODULO

        # update active blocks
        if current_position in block_ending_positions:
            block_that_ended = active_blocks.popleft()
            alpha -= possibilities[block_starts[block_that_ended] - 1]

        current_position += 1


def main():
    handle_input()
    stops = turn_input_into_blocks()
    compute_possibilities(build_stops_iterator(stops))
    print possibilities[n - 1]


if __name__ == '__main__':
    main()