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: Time Limit Exceeded

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):
        # 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)
            # Do all active blocks move more to left?
            all_blocks_move_to_left = True
            for block_id in active_blocks:
                block_start = takahashis[block_id].block_start
                if block_start >= i:
                    all_blocks_move_to_left = False
            if all_blocks_move_to_left:
                result += possibilities[i - 1]


        possibilities[i] = result % MODULO



turn_input_into_blocks()
# print block_starting_positions
# print block_ending_positions
compute_possibilities()
print possibilities[n-1]

Submission status: Accepted

Solution code:
class BIT():
    def __init__(self,n,mod):
        self.BIT=[0]*(n+1)
        self.num=n
        self.mod=mod

    def query(self,idx):
        res_sum = 0
        mod=self.mod
        while idx > 0:
            res_sum += self.BIT[idx]
            res_sum%=mod
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        mod=self.mod
        while idx <= self.num:
            self.BIT[idx] += x
            self.BIT[idx]%=mod
            idx += idx&(-idx)
        return

import sys,bisect

input=sys.stdin.readline

mod=10**9+7
inv=pow(2,mod-2,mod)

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

const=[]
for i in range(1,N+1):
    R=bisect.bisect_right(cummin,V[i])-1
    L=bisect.bisect_left(cummax,V[i])
    const.append((L,R))


Lconst=[(i,10**15) for i in range(N+1)]
for L,R in const:
    pL,pR=Lconst[L]
    Lconst[L]=(L,min(R,pR))

_const=[]
for i in range(1,N+1):
    L,R=Lconst[i]
    if R!=10**15:
        _const.append((L,R))

const=[]
for L,R in _const:
    while const and const[-1][1]>=R:
        const.pop()
    const.append((L,R))


M=len(const)
const=[(-10**15,0)]+const
Rconst=[const[i][1] for i in range(M+1)]
B=BIT(M,mod)
dp=[1]*(M+1)
for i in range(1,M+1):
    L,R=const[i]
    id=bisect.bisect_left(Rconst,L)
    res=(B.query(i-1)-B.query(id-1))%mod
    l,r=const[id]
    l=max(l,Rconst[id-1]+1)
    res+=dp[id-1]*(pow(2,r-L+1,mod)-1)*pow(2,L-l,mod)%mod
    res%=mod
    dp[i]=res
    if i!=M:
        nR=Rconst[i+1]
        add=dp[i]*(pow(2,nR-R,mod)-1)%mod
        add%=mod
        B.update(i,add)

cnt=0
data=[0]*(N+2)
for i in range(1,M+1):
    L,R=const[i]
    data[L]+=1
    data[R+1]+=-1
for i in range(1,N+2):
    data[i]+=data[i-1]
for i in range(1,N+1):
    if data[i]==0:
        cnt+=1
ans=pow(2,cnt,mod)*dp[M]
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
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()

Submission status: Runtime Error

Solution code:
import sys

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

newV=[]
for i in range(1,N+1):
    if not (V[i]>cummax[i-1] and cummin[i+1]>V[i]):
        newV.append(V[i])

V=newV
N=len(V)
all=pow(2,N,mod)
highid,lowid=-1,-1
Vmax=cummax[-2]
Vmin=cummin[1]
for i in range(0,N):
    if V[i]==Vmax:
        highid=i+1
    elif V[i]==Vmin:
        lowid=i+1

if highid!=-1 and lowid!=-1:
    high=pow(2,highid-1,mod)
    low=pow(2,N-lowid,mod)
    if highid>lowid:
        highlow=pow(2,N+1-highid-lowid,mod)
    else:
        highlow=1
    ans=all+highlow-high-low
    print(ans%mod)
elif highid==-1 and lowid!=-1:
    low=pow(2,N-lowid,mod)
    ans=all-low
    print(ans%mod)
elif highid!=-1 and lowid==-1:
    high=pow(2,highid-1,mod)
    ans=ans-high
    print(ans%mod)
else:
    print(all)

Submission status: Runtime Error

Solution code:
import sys

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

newV=[]
for i in range(1,N+1):
    if not (V[i]>cummax[i-1] and cummin[i+1]>V[i]):
        newV.append(V[i])

V=newV
N=len(V)
all=pow(2,N,mod)
highid,lowid=-1,-1
Vmax=cummax[-2]
Vmin=cummin[1]
for i in range(0,N):
    if V[i]==Vmax:
        highid=i+1
    elif V[i]==Vmin:
        lowid=i+1

if high!=-1 and low!=-1:
    high=pow(2,highid-1,mod)
    low=pow(2,N-lowid,mod)
    if highid>lowid:
        highlow=pow(2,N+1-highid-lowid,mod)
    else:
        highlow=1
    ans=all+highlow-high-low
    print(ans%mod)
elif high==-1 and low!=-1:
    low=pow(2,N-lowid,mod)
    ans=all-low
    print(ans%mod)
elif high!=-1 and low==-1:
    high=pow(2,highid-1,mod)
    ans=ans-high
    print(ans%mod)
else:
    print(all)

Submission status: Runtime Error

Solution code:
import sys

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

newV=[]
for i in range(1,N+1):
    if not (V[i]>cummax[i-1] and cummin[i+1]>V[i]):
        newV.append(V[i])

V=newV
N=len(V)
all=pow(2,N,mod)
highid,lowid=-1,-1
Vmax=cummax[-2]
Vmin=cummin[1]
for i in range(0,N):
    if V[i]==Vmax:
        highid=i+1
    elif V[i]==Vmin:
        lowid=i+1
high=pow(2,highid-1,mod)
low=pow(2,N-lowid,mod)
if highid>lowid:
    highlow=pow(2,N+1-highid-lowid,mod)
else:
    highlow=1
ans=all+highlow-high-low
print(ans%mod)

Submission status: Runtime Error

Solution code:
import sys

input=sys.stdin.readline

mod=10*9+7

N=int(input())
taka=[tuple(map(int,input().split())) for i in range(N)]
taka.sort()

V=[0]+[taka[i][1] for i in range(N)]+[10**15]
cummin=[V[i] for i in range(N+2)]
for i in range(N,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])
cummax=[V[i] for i in range(N+2)]
for i in range(1,N+2):
    cummax[i]=max(cummax[i],cummax[i-1])

cnt=0
for i in range(1,N+1):
    if V[i]>cummax[i-1] and cummin[i+1]>V[i]:
        cnt+=1

if cnt:
    print(pow(2,N-cnt,mod))
else:
    all=pow(2,N,mod)
    highid,lowid=-1,-1
    Vmax=cummax[-2]
    Vmin=cummin[1]
    for i in range(1,N+1):
        if V[i]==Vmax:
            highid=i
        elif V[i]==Vmin:
            lowid=i
    high=pow(2,highid-1,mod)
    low=pow(2,N-lowid,mod)
    if highid>lowid:
        highlow=pow(2,N+1-highid-lowid,mod)
    else:
        highlow=1
    ans=all+highlow-high-low
    print(ans%mod)

Submission status: Runtime Error

Solution code:
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()