Problem:


Score : 1200 points

Problem Statement

Takahashi is an expert of Clone Jutsu, a secret art that creates copies of his body.

On a number line, there are N copies of Takahashi, numbered 1 through N.
The i-th copy is located at position X_i and starts walking with velocity V_i in the positive direction at time 0.

Kenus is a master of Transformation Jutsu, and not only can he change into a person other than himself, but he can also transform another person into someone else.

Kenus can select some of the copies of Takahashi at time 0, and transform them into copies of Aoki, another Ninja.
The walking velocity of a copy does not change when it transforms.
From then on, whenever a copy of Takahashi and a copy of Aoki are at the same coordinate, that copy of Takahashi transforms into a copy of Aoki.

Among the 2^N ways to transform some copies of Takahashi into copies of Aoki at time 0, in how many ways will all the copies of Takahashi become copies of Aoki after a sufficiently long time?
Find the count modulo 10^9+7.

Constraints

1 ≤ N ≤ 200000

1 ≤ X_i,V_i ≤ 10^9(1 ≤ i ≤ N)

X_i and V_i are integers.

All X_i are distinct.

All V_i are distinct.

Input

The input is given from Standard Input in the following format:

N
X_1 V_1
:
X_N V_N

Output

Print the number of the ways that cause all the copies of Takahashi to turn into copies of Aoki after a sufficiently long time, modulo 10^9+7.

Sample Input 1

3
2 5
6 1
3 7

Sample Output 1

6

All copies of Takahashi will turn into copies of Aoki after a sufficiently long time if Kenus transforms one of the following sets of copies of Takahashi into copies of Aoki: (2), (3), (1,2), (1,3), (2,3) and (1,2,3).

Sample Input 2

4
3 7
2 9
8 16
10 8

Sample Output 2

9



Sample input:
3
2 5
6 1
3 7


Sample output:
6

Submission status: Wrong Answer

Solution code:
from bisect import bisect, bisect_left
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):
    def __init__(self, position, velocity):
        self.position = position
        self.velocity = velocity
        self.block_start = None
        self.block_end = None

    def set_block(self, start, end):
        self.block_start = start
        self.block_end = end

    def __repr__(self):
        return str({
            'position': self.position,
            'velocity': self.velocity,
            'block_start': self.block_start,
            'block_end': self.block_end
        })


class FirstNumberFinder(object):
    """Given a number in a sequence, it finds the first larger
    number from the start; or the first smaller number from the end."""
    def __init__(self, sequence, reversed_sequence=None, n=None):
        if not n:
            n = len(sequence)
        if not reversed_sequence:
            reversed_sequence = reversed(sequence)

        # find largest numbers
        b = []
        largest = -1
        for index, number in enumerate(sequence):
            if number > largest:
                b.append((number, index))
                largest = number
        b.sort()
        self.largest_numbers, self.largest_indices = zip(*b)
        # array for fast lookup
        self.largest = []
        for i, number in enumerate(self.largest_numbers):
            if i < len(self.largest_numbers) - 1:
                repeat_count = self.largest_indices[i + 1] - self.largest_indices[i]
            else:
                repeat_count = n - self.largest_indices[i]
            self.largest += [number] * repeat_count

        # find smallest numbers
        b = []
        smallest = 1000000001
        for index, number in enumerate(reversed_sequence):
            if number < smallest:
                b.append((number, n - index - 1))
                smallest = number
        b.sort()
        self.smallest_numbers, self.smallest_indices = zip(*b)
        # array for fast lookup
        self.smallest = []
        for i, number in enumerate(self.smallest_numbers):
            if i > 0:
                repeat_count = self.smallest_indices[i] - self.smallest_indices[i - 1]
            else:
                repeat_count = self.smallest_indices[0] + 1
            self.smallest += [number] * repeat_count

    def find_larger_from_start(self, number):
        """Returns tuple. First larger number and its index position in sequence from start."""
        index = bisect_left(self.largest_numbers, number)
        if index >= 0:
            return (self.largest_numbers[index], self.largest_indices[index])

    def find_smaller_from_end(self, number):
        """Returns tuple. First smaller number and its index position in sequence from end."""
        index = bisect(self.smallest_numbers, number) - 1
        if index >= 0:
            return (self.smallest_numbers[index], self.smallest_indices[index])


takahashis = []
blocks = []
block_starting_positions = dict()
block_ending_positions = dict()


# HANDLE INPUT
n = int(iterator.next())
for i in xrange(n):
    x, v = iterator.next().split()
    t = Takahashi(int(x), int(v))
    takahashis.append(t)


def turn_input_into_blocks():
    takahashis.sort(key=lambda takahashi: takahashi.position)
    number_finder = FirstNumberFinder(
        sequence=(t.velocity for t in takahashis),
        reversed_sequence=(t.velocity for t in reversed(takahashis)),
        n=n)
    for i, t in enumerate(takahashis):
        # find beginning of block
        if number_finder.largest[i] <= t.velocity:
            block_start = i
        else:
            larger_number, larger_number_index = number_finder.find_larger_from_start(t.velocity)
            block_start = larger_number_index

        # find end of block
        if number_finder.smallest[i]  >= t.velocity:
            block_end = i
        else:
            smaller_number, smaller_number_index = number_finder.find_smaller_from_end(t.velocity)
            block_end = smaller_number_index

        t.set_block(block_start, block_end)

        # add to block list if is current shortest
        saved_block_start_id = block_starting_positions.get(block_start)
        saved_block_end_id = block_ending_positions.get(block_end)
        test1 = (
            saved_block_start_id is None or
            block_end < takahashis[saved_block_start_id].block_end)
        test2 = (
            saved_block_end_id is None or
            block_start > takahashis[saved_block_end_id].block_start)

        if test1 and test2:
            block_starting_positions[block_start] = i
            block_ending_positions[block_end] = i
            if saved_block_start_id is not None:
                removed_block_end = takahashis[saved_block_start_id].block_end
                if block_ending_positions.get(removed_block_end) == saved_block_start_id:
                    del block_ending_positions[removed_block_end]
            if saved_block_end_id is not None:
                removed_block_start = takahashis[saved_block_end_id].block_start
                if block_starting_positions.get(removed_block_start) == saved_block_end_id:
                    del block_starting_positions[removed_block_start]


# possibilities[i] indicates the number of possibilities
# from block with indices 0 to i.
possibilities = [1] * (n + 1)



def compute_possibilities():
    # initialization hack, since index starts at 0
    possibilities[-1] = 1

    active_blocks = []

    for i in xrange(n):
        t = takahashis[i]

        # update active blocks
        block_id = block_ending_positions.get(i - 1)
        if block_id is not None:
            active_blocks.remove(block_id)
        block_id = block_starting_positions.get(i)
        if block_id is not None:
            active_blocks.append(block_id)

        if not active_blocks:
            # This Takahashi can be set arbitrarily to Aoki or not
            result = 2 * possibilities[i - 1]

        else:
            # SET i to AOKI
            # Possibilities we have guaranteed
            result = possibilities[i - 1]

            # Other possibilities, we might get by zeroing blocks going into i
            for block_id in active_blocks:
                block_start = takahashis[block_id].block_start
                if block_start < i:
                    result += possibilities[block_start - 1]


            # SET i NOT to AOKI (or explore if possible)
            # Does i's block move into left?
            if t.block_start < i:
                result += possibilities[i - 1]


        possibilities[i] = result % MODULO



turn_input_into_blocks()


# print block_starting_positions
# print block_ending_positions


compute_possibilities()
# print possibilities
print possibilities[n-1]

Submission status: Wrong Answer

Solution code:
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 = 1e9
MAX_N = 200000
MODULO =  1000000007


class Takahashi(object):
    def __init__(self, position, velocity):
        self.position = position
        self.velocity = velocity
        self.block_start = None
        self.block_end = None

    def set_block(self, start, end):
        self.block_start = start
        self.block_end = end

    def __repr__(self):
        return str({
            'position': self.position,
            'velocity': self.velocity,
            'block_start': self.block_start,
            'block_end': self.block_end
        })


takahashis = []
blocks = []
block_starting_positions = dict()
block_ending_positions = dict()


# HANDLE INPUT
n = int(iterator.next())
for i in xrange(n):
    x, v = map(int, iterator.next().split())
    t = Takahashi(x, v)
    takahashis.append(t)


def turn_input_into_blocks():
    takahashis.sort(key=lambda takahashi: takahashi.position)
    n = len(takahashis)

    # set smallest velocities for all i
    smallest_velocities = [None] * n
    smallest_velocity = MAX_VELOCITY + 1
    for k, t in enumerate(reversed(takahashis)):
        i = n - k - 1
        smallest_velocity = min(smallest_velocity, t.velocity)
        smallest_velocities[i] = smallest_velocity

    largest_velocity = 0
    for i, t in enumerate(takahashis):
        # find beginning of block
        largest_velocity = max(largest_velocity, t.velocity)
        if largest_velocity <= t.velocity:
            block_start = i
        else:
            for j in xrange(i + 1):
                if takahashis[j].velocity >= t.velocity:
                    block_start = j
                    break

        # find end of block
        if smallest_velocities[i] >= t.velocity:
            block_end = i
        else:
            for j in xrange(n - 1, i - 1, -1):
                if takahashis[j].velocity <= t.velocity:
                    block_end = j
                    break

        t.set_block(block_start, block_end)

        # add to block list if is current shortest
        saved_block_start_id = block_starting_positions.get(block_start)
        saved_block_end_id = block_ending_positions.get(block_end)
        test1 = (
            saved_block_start_id is None or
            block_end < takahashis[saved_block_start_id].block_end)
        test2 = (
            saved_block_end_id is None or
            block_start > takahashis[saved_block_end_id].block_start)

        if test1 and test2:
            block_starting_positions[block_start] = i
            block_ending_positions[block_end] = i
            if saved_block_start_id is not None:
                removed_block_end = takahashis[saved_block_start_id].block_end
                if block_ending_positions.get(removed_block_end) == saved_block_start_id:
                    del block_ending_positions[removed_block_end]
            if saved_block_end_id is not None:
                removed_block_start = takahashis[saved_block_end_id].block_start
                if block_starting_positions.get(removed_block_start) == saved_block_end_id:
                    del block_starting_positions[removed_block_start]


# possibilities[i] indicates the number of possibilities
# from block with indices 0 to i.
possibilities = [1] * (n + 1)



def compute_possibilities():
    # initialization hack, since index starts at 0
    possibilities[-1] = 1

    active_blocks = []

    for i in xrange(n):
        t = takahashis[i]

        # update active blocks
        block_id = block_ending_positions.get(i - 1)
        if block_id is not None:
            active_blocks.remove(block_id)
        block_id = block_starting_positions.get(i)
        if block_id is not None:
            active_blocks.append(block_id)

        if not active_blocks:
            # This Takahashi can be set arbitrarily to Aoki or not
            result = 2 * possibilities[i - 1]

        else:
            # SET i to AOKI
            # Possibilities we have guaranteed
            result = possibilities[i - 1]

            # Other possibilities, we might get by zeroing blocks going into i
            for block_id in active_blocks:
                block_start = takahashis[block_id].block_start
                if block_start < i:
                    result += possibilities[block_start - 1]


            # SET i NOT to AOKI (or explore if possible)
            # Does i's block move into left?
            if t.block_start < i:
                result += possibilities[i - 1]


        possibilities[i] = result % MODULO



turn_input_into_blocks()


# print block_starting_positions
# print block_ending_positions


compute_possibilities()
# print possibilities
print possibilities[n-1]

Submission status: Time Limit Exceeded

Solution code:
from collections import OrderedDict, deque
import heapq
import fileinput


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 file_iterator(file_name):
    with open(file_name) as f:
        for line in f:
            yield line


def handle_input(file_name=None):
    if file_name:
        iterator = file_iterator(file_name)
    else:
        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))


def preprocessing():
    takahashis.sort()
    block_starts[:] = [None] * n
    block_ends[:] = [None] * n
    seen[:] = [False] * n
    possibilities[:] = [None] * (n + 1)
    velocities[:] = ((t[1], i) for i, t in enumerate(takahashis))
    velocities.sort()


def turn_input_into_blocks():
    velocity_cursor = -1
    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
        current_velocity = takahashis[i][1]
        first = True
        while velocity_cursor < n - 1 and current_velocity >= 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

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


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

    return possibilities[n - 1]


def main():
    handle_input()
    preprocessing()
    stops = turn_input_into_blocks()
    return compute_possibilities(build_stops_iterator(stops))


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

Submission status: Time Limit Exceeded

Solution code:
from collections import OrderedDict
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):
#     def __init__(self, position, velocity):
#         self.position = position
#         self.velocity = velocity
#         self.block_start = None
#         self.block_end = None

#     def set_block(self, start, end):
#         self.block_start = start
#         self.block_end = end

#     def __repr__(self):
#         return str({
#             'position': self.position,
#             'velocity': self.velocity,
#             'block_start': self.block_start,
#             'block_end': self.block_end
#         })


# HANDLE INPUT
n = int(iterator.next())
takahashis = [None] * n

for i in xrange(n):
    x, v = iterator.next().split()
    takahashis[i] = (int(x), int(v))
takahashis.sort()


# maps a block index (0...N-1) to start (or end) of its corresponding block.
block_starts = [None] * n
block_ends = [None] * n
# maps a position (0...N-1) to an index of a block, which starts (or ends) there.
block_starting_positions = OrderedDict()
block_ending_positions = OrderedDict()



def turn_input_into_blocks():
    # number_finder = FirstNumberFinder(
    #     sequence=(t[1] for t in takahashis),
    #     reversed_sequence=(t[1] for t in reversed(takahashis)),
    #     n=n)
    seen = [False] * n
    rightmost_smaller_velocity_index = 0
    sorted_velocities = [(t[1], i) for i, t in enumerate(takahashis)]
    sorted_velocities.sort(reverse=True)

    for i, velocity in enumerate((t[1] for t in takahashis)):
        #print i, rightmost_smaller_velocity_index
        #print seen
        # Was there a larger velocity before already?
        if seen[i]:
            continue
        # OK, this is the largest one so far.

        block_start = i
        # Determine end of block involving the smallest unseen velocity.
        # Also, get index of rightmost smaller velocity and mark as seen
        first = True
        while sorted_velocities and velocity >= sorted_velocities[-1][0]:
            upcoming_smaller_velocity, upcoming_smaller_velocity_index = sorted_velocities.pop()
            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

        #print rightmost_smaller_velocity_index
        #print sorted_velocities

        block_starts[i] = block_start
        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:
            block_starting_positions
            del block_starting_positions[block_starts[previous_longer_block]]
        block_starting_positions[block_start] = i
        block_ending_positions[block_end] = i

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



# possibilities[i] indicates the number of possibilities
# from block with indices 0 to i.
possibilities = [None] * (n + 1)

def compute_possibilities():
    # initialization hack, since index starts at 0
    possibilities[-1] = 1

    active_blocks = []
    def move_active_cursor_forwards(last_position, current_position):
        block_id = block_ending_positions.get(last_position)
        if block_id is not None:
            active_blocks.remove(block_id)
        block_id = block_starting_positions.get(current_position)
        if block_id is not None:
            active_blocks.append(block_id)

    def move_active_cursor_backwards(current_position, last_position):
        block_id = block_ending_positions.get(last_position)
        if block_id is not None:
            active_blocks.append(block_id)
        block_id = block_starting_positions.get(current_position)
        if block_id is not None:
            active_blocks.remove(block_id)

    def empty_gap_possibilities(possibilities_before_gap, gap_length):
        return (possibilities_before_gap * 2**gap_length) % MODULO

    def uniform_piece_possibilities_1(possibilities_at_first_index, gap_length):
        """Uniform piece was started by a new block."""
        return (possibilities_at_first_index * (2**gap_length - 1)) % MODULO

    def uniform_piece_possibilities_2(
        possibilities_before_gap, possibilities_at_first_index, gap_length):
        """Uniform piece was started by a block being removed."""
        p0, p1 = possibilities_before_gap, possibilities_at_first_index
        return (p1 * (2**gap_length - 1) - p0 * (2**gap_length - 2)) % MODULO

    def one_step_change_possibilities(i, possibilities, active_blocks):
        # SET i to AOKI
        # Possibilities we have guaranteed
        result = possibilities[i - 1]
        #print 'b'
        #print possibilities
        #print i
        #print result

        # Other possibilities, we might get by zeroing blocks going into i
        for block_id in active_blocks:
            block_start = block_starts[block_id]
            if block_start < i:
                result += possibilities[block_start - 1]

        # SET i NOT to AOKI (or explore if possible)
        # Do all active blocks move more to left? (Includes zero blocks.)
        all_blocks_move_to_left = True
        for block_id in active_blocks:
            block_start = block_starts[block_id]
            if block_start >= i:
                all_blocks_move_to_left = False
        if all_blocks_move_to_left:
            result += possibilities[i - 1]

        return result % MODULO


    # #print block_starting_positions
    # #print block_ending_positions

    POSITION_TYPE_START = 1
    POSITION_TYPE_END = 2
    last_position = -1
    last_position_type = None
    for position in blocks_iterator:
        # Sometimes a block has size 1.
        if position <= last_position:
            continue


        move_active_cursor_forwards(last_position, position)


        #print 'start'
        #print position, last_position
        #print active_blocks
        #print '---'


        indices_moved = position - last_position
        p = possibilities[last_position]
        i = position

        # PROCESS BLOCK START
        if position in block_starting_positions:
            if indices_moved > 1:
                # no blocks in earlier gap
                if len(active_blocks) == 1:
                    #print 'a'
                    possibilities[i - 1] = empty_gap_possibilities(p, indices_moved - 1)
                # one or more long blocks in earlier gap
                elif last_position_type == POSITION_TYPE_START:
                    possibilities[i - 1] = uniform_piece_possibilities_1(p, indices_moved)
                elif last_position_type == POSITION_TYPE_END:
                    move_active_cursor_backwards(position, last_position)
                    move_active_cursor_forwards(last_position, last_position + 1)
                    p1 = one_step_change_possibilities(last_position + 1, possibilities, active_blocks)
                    move_active_cursor_forwards(last_position + 1, position)
                    possibilities[i - 1] = uniform_piece_possibilities_2(p, p1, indices_moved - 1)

            # compute i-th position too now.
            possibilities[i] = one_step_change_possibilities(i, possibilities, active_blocks)
            last_position = i
            last_position_type = POSITION_TYPE_START

        # PROCESS BLOCK END
        elif position in block_ending_positions:
            if indices_moved == 1:
                possibilities[i] = one_step_change_possibilities(i, possibilities, active_blocks)
            elif last_position_type == POSITION_TYPE_START:
                possibilities[i] = uniform_piece_possibilities_1(p, indices_moved + 1)
            elif last_position_type == POSITION_TYPE_END:
                move_active_cursor_backwards(position, last_position)
                move_active_cursor_forwards(last_position, last_position + 1)
                p1 = one_step_change_possibilities(last_position + 1, possibilities, active_blocks)
                move_active_cursor_forwards(last_position + 1, position)
                #print '%', p, p1, indices_moved
                possibilities[i] = uniform_piece_possibilities_2(p, p1, indices_moved)

            last_position = i
            last_position_type = POSITION_TYPE_END

        # PROCESS SENTINEL
        else:
            possibilities[i] = empty_gap_possibilities(p, indices_moved)
            last_position = i
            last_position_type = None



blocks_iterator = turn_input_into_blocks()


#print block_starting_positions
#print block_ending_positions

compute_possibilities()

#print possibilities
print possibilities[n-1]