Problem p03033 (python)

Fixed submission:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,Q = list(map(int,input().split()))

    road = []
    x_list = []

    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append([0,s-x,x])
        road.append([1,t-x,x])

    for i in range(Q):
        road.append([2,int(input()),i])

    from collections import defaultdict

    counter = defaultdict(int)
    counter[10**27] = 1
    ans = [0]*Q

    road.sort(key=lambda x:x[0])
    road.sort(key=lambda x:x[1])

    q = [10**27]

    from heapq import heappop,heappush

    for id,_,x in road:
        if id==0:
            heappush(q,x)
            counter[x]+=1
        elif id==1:
            counter[x]-=1
        else:
            while counter[q[0]]==0:
                heappop(q)
            #print(q)
            if q[0]<10**27:
                ans[x] = q[0]
            else:
                ans[x] = -1
    print("\n".join(map(str,ans)))

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
"""
Created on Fri Aug  9 00:23:59 2019

@author: miz18
"""

import sys
input = sys.stdin.readline

def main(): 
    N,Q = list(map(int,input().split()))
     
    road = []
    r_append = road.append
    x_list = []
    x_append = x_list.append
    for i in range(N):
        s,t,x = list(map(int,input().split()))
        r_append(("s",s-x,x,0))
        r_append(("t",t-x,x,0))
        x_append.append(x)
     
    for i in range(Q):
        d = int(input())
        r_append(("m",d,i,1))
     
    road.sort(lambda x:x[3])
    road.sort(lambda x:x[1])
     
    x_list = list(set(x_list))
    x_list.sort()
     
    x2i_dict = {}
    for i,x in enumerate(x_list):
        x2i_dict[x]=i
     
     
    class BIT:
                
        def __init__(self, L):
            self.N = len(L)
            self.bit = [0]*self.N
            for i,l in enumerate(L):
                self.add(i,l)
     
        def add(self, a, w):
            x = a + 1
            for i in range(1000):
                self.bit[x-1] += w
                x += x & -x
                if x > self.N:
                    break
     
        def sum(self, a):
            x = a+1
            ret = 0
            for i in range(1000):
                ret += self.bit[x-1]
                x -= x & -x
                if x <= 0:
                    break        
            return ret
     
    def bisectR(l,r,bit):
        while r-l>1:
            if bit.sum((l+r)//2)>0:
                r = (l+r)//2
            else:
                l = (l+r)//2
        return r
     
    
     
    bit = BIT([0]*len(x_list))
    b_add = bit.add
    
    ans = [0]*Q
    for r in road:
        if r[0]=="s":
            b_add(x2i_dict[r[2]],1)
        elif r[0]=="t":
            b_add(x2i_dict[r[2]],-1)
        else:
            if bit.sum(len(x_list)-1)==0:
                ans[r[2]]=-1
            elif bit.sum(0)>0:
                ans[r[2]]=x_list[0]
            else:
                i = bisectR(0,len(x_list)-1,bit)
                ans[r[2]] = x_list[i]
     
    for a in ans:
        print(a)
        
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):

import sys
input = sys.stdin.readline

def main():
    N,Q = list(map(int,input().split()))

    road = []
    x_list = []
    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append((s-x,x,0))
        road.append((t-x,x,1))
        x_list.append(x)

    for i in range(Q):
        d = int(input())
        road.append((d,i,2))

    road.sort(lambda x:x[2])
    road.sort(lambda x:x[0])

    x_list = list(set(x_list))
    x_list.sort()

    x2i_dict = {}
    for i,x in enumerate(x_list):
        x2i_dict[x]=i


    class BIT:
            
        def __init__(self, L):
            self.N = len(L)
            self.bit = [0]*self.N
            for i,l in enumerate(L):
                self.add(i,l)

        def add(self, a, w):
            x = a + 1
            for i in range(1000):
                self.bit[x-1] += w
                 x += x & -x
                if x > self.N:
                    break

        def sum(self, a):
            x = a+1
            ret = 0
            for i in range(1000):
                ret += self.bit[x-1]
                x -= x & -x
                if x <= 0:
                    break        
           return ret


    bit = BIT([0]*xn)
    bitadd = bit.add
    bitsum = bit.sum
    def bisectR(l,r,bit):
        while r-l>1:
            if bitsum((l+r)//2)>0:
                r = (l+r)//2
            else:
                l = (l+r)//2
        return r

    xn=len(x_list)

    ans = [0]*Q
    for r in road:
        if r[2]==0:
             bitadd(x2i_dict[r[1]],1)
        elif r[2]==1:
            bitadd(x2i_dict[r[1]],-1)
        else:
            if bitsum(xn-1)==0:
               ans[r[1]]=-1
            elif bitsum(0)>0:
                ans[r[1]]=x_list[0]
            else:
                i = bisectR(0,xn-1)
                ans[r[1]] = x_list[r]
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

import sys
input = sys.stdin.readline

N,Q = list(map(int,input().split()))

road = []
x_list = []
for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append((s-x,x,0))
    road.append((t-x,x,1))
    x_list.append(x)

for i in range(Q):
    d = int(input())
    road.append((d,i,2))

road.sort(lambda x:x[2])
road.sort(lambda x:x[0])

x_list = list(set(x_list))
x_list.sort()

x2i_dict = {}
for i,x in enumerate(x_list):
    x2i_dict[x]=i


class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret


bit = BIT([0]*xn)

def bisectR(l,r,bit):
    while r-l>1:
        if bit.sum((l+r)//2)>0:
            r = (l+r)//2
        else:
            l = (l+r)//2
    return r

xn=len(x_list)

ans = [0]*Q
for r in road:
    if r[2]==0:
        bit.add(x2i_dict[r[1]],1)
    elif r[2]==1:
        bit.add(x2i_dict[r[1]],-1)
    else:
        if bit.sum(xn-1)==0:
            ans[r[1]]=-1
        elif bit.sum(0)>0:
            ans[r[1]]=x_list[0]
        else:
            i = bisectR(0,xn-1)
            ans[r[1]] = x_list[r]
for a in ans:
    print(a)