time_series_queries.py

#!/bin/python

import sys
import bisect

def type_1_query(tv, value, minimum_time_to_right):
    # find the position of the minimum value
    pos = bisect.bisect_left(tv, (value, -1))
    # print "min ", value, " at idx", pos
    # sort all valid member based on time
    if pos >= len(minimum_time_to_right):
        # print pos, -1
        print -1
        return
    # print ans, tv[ans]
    print minimum_time_to_right[pos]


if __name__ == "__main__":
    n, q = map(int, raw_input().strip().split(' '))
    ints = []
    while True:
        try:
            line = map(int, raw_input().strip().split())
            ints.extend(line)
        except:
            break
    t = ints[:n]
    p = ints[n:2*n]
    tv = []
    for i, val in enumerate(t):
        tv.append((p[i], val))
    tv.sort()
    # tv (value, time) 
    minimum_time_to_right = []
    for i, (value, time) in enumerate(reversed(tv)):
        if i == 0:
            minimum_time_to_right.append(time)
        else:
            minimum_time_to_right.append(min(minimum_time_to_right[i-1], time))
    minimum_time_to_right = list(reversed(minimum_time_to_right))

    maximum_value_to_right = []
    for i, v in enumerate(reversed(p)):
        if i == 0:
            maximum_value_to_right.append(v)
        else:
            maximum_value_to_right.append(max(maximum_value_to_right[i-1], v))
    maximum_value_to_right = list(reversed(maximum_value_to_right))
    queries = []
    for i in xrange(2*n, len(ints), 2):
        _type, value = ints[i], ints[i+1]
        if _type == 1:
            type_1_query(tv, value, minimum_time_to_right)
        elif _type == 2:
            pos = bisect.bisect_left(t, value)
            if pos >= len(maximum_value_to_right):
                print -1
            else:
                print maximum_value_to_right[pos]
        else:
            assert False