Problem:


Score : 500 points

Problem Statement

There is an infinitely long street that runs west to east, which we consider as a number line.

There are N roadworks scheduled on this street.
The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.

Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.

Find the distance each of the Q people will walk.

Constraints

All values in input are integers.

1 \leq N, Q \leq 2 \times 10^5

0 \leq S_i < T_i \leq 10^9

1 \leq X_i \leq 10^9

0 \leq D_1 < D_2 < ... < D_Q \leq 10^9

If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

Input

Input is given from Standard Input in the following format:

N Q
S_1 T_1 X_1
:
S_N T_N X_N
D_1
:
D_Q

Output

Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.

Sample Input 1

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

Sample Output 1

2
2
10
-1
13
-1

The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.

The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.

The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.



Sample input:
4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8


Sample output:
2
2
10
-1
13
-1

Submission status: Time Limit Exceeded

Solution code:
n, q = [int(i) for i in input().split()]
roadworks = []
for _ in range(n):
    roadworks.append([int(i) for i in input().split()])
roadworks.sort(key=lambda r: r[2])

starts = []
for _ in range(q):
    starts.append(int(input()))

computed = {}
for d in starts:
    if d in computed:
        print(computed[d])
        continue

    will_stop = False
    day = d
    pos = 0
    for r in roadworks:
        day += r[2] - pos
        pos = r[2]
        if day < r[0] or day >= r[1]:
            continue
        else:
            will_stop = True
            break
    computed[d] = pos if will_stop else -1
    print(pos if will_stop else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append((s-x,1,x))
    E.append((t-x,0,x))

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heappush(H,x)
    elif type_==0:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
input = sys.stdin.readline
#import numpy as np

 

 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append((s-x,1,x))
    E.append((t-x,0,x))

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_&1:
        S.add(x)
        heappush(H,x)
    elif not type_:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 

 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append((s-x,1,x))
    E.append((t-x,0,x))

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_&1:
        S.add(x)
        heappush(H,x)
    elif not type_:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
from heapq import heappop,heappush
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append((s-x,1,x))
    E.append((t-x,-1,x))

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append((s-x,1,x))
    E.append((t-x,-1,x))

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heapq.heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x,1,x])
    E.append([t-x,-1,x])

for a in range(Q):
    E.append([int(input()),2,0])
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heapq.heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        #if(x in S):print(7329847)
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heapq.heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:(x[0],x[1]))
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        #if(x in S):print(7329847)
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heapq.heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
readline = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num


#main
def solve():
    return

#入力
N,Q=map(int,input().split())

E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])

S=set()
H=[]
for a in E:
    x=a[2]
    type_=a[1]
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        if len(S)==0:
            print(-1)
        else:
            while H[0] not in S:
                heapq.heappop(H)
            print(H[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
readline = sys.stdin.buffer.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num


#main
def solve():
    return

#入力
N,Q=map(int,input().split())

E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])

S=set()
H=[]
for a in E:
    x=a[2]
    type_=a[1]
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        if len(S)==0:
            print(-1)
        else:
            while H[0] not in S:
                heapq.heappop(H)
            print(H[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num


#main
def solve():
    return

#入力
N,Q=map(int,input().split())

E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])

S=set()
H=[]
for a in E:
    x=a[2]
    type_=a[1]
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        if len(S)==0:
            print(-1)
        else:
            while H[0] not in S:
                heapq.heappop(H)
            print(H[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num


#main
def solve():
    return

#入力
N,Q=map(int,input().split())
S=[0]*N
T=[0]*N
X=[0]*N

for a in range(N):
    S[a],T[a],X[a]=map(int,input().split())


E=[]
for a in range(N):
    E.append([S[a]-X[a]-0.5,1,X[a]])
    E.append([T[a]-X[a]-0.5,-1,X[a]])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])


S=set()
H=[]
for a in E:
    x=a[2]
    val=a[0]
    type_=a[1]
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        if len(S)==0:
            print(-1)
        else:
            while H[0] not in S:
                heapq.heappop(H)
            print(H[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num


#main
def solve():
    return

#入力
N,Q=map(int,input().split())
S=[0]*N
T=[0]*N
X=[0]*N

D=[]
for a in range(N):
    S[a],T[a],X[a]=map(int,input().split())


E=[]
for a in range(N):
    E.append([S[a]-X[a],1,X[a]])
    E.append([T[a]-X[a]-0.5,-1,X[a]])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])


S=set()
H=[]
for a in E:
    x=a[2]
    val=a[0]
    type_=a[1]
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        if len(S)==0:
            print(-1)
        else:
            while H[0] not in S:
                heapq.heappop(H)
            print(H[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num


#main
def solve():
    return

#入力
N,Q=map(int,input().split())
S=[0]*N
T=[0]*N
X=[0]*N

D=[]
for a in range(N):
    S[a],T[a],X[a]=map(int,input().split())


E=[]
for a in range(N):
    E.append([S[a]-X[a],1,X[a]])
    E.append([T[a]-X[a],-1,X[a]])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])


S=set()
H=[]
for a in E:
    x=a[2]
    val=a[0]
    type_=a[1]
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        S.remove(x)
    else:
        if len(S)==0:
            print(-1)
        else:
            while H[0] not in S:
                heapq.heappop(H)
            print(H[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import time
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num


#main
def solve():
    return

#入力
N,Q=map(int,input().split())
A=[{} for a in range(N)]
D=[]
for a in range(N):
    s,t,x=map(int,input().split())
    A[a]["s"]=s
    A[a]["t"]=t
    A[a]["x"]=x
for a in range(Q):
    D.append(-int(input()))
A.sort(key=lambda x:x["x"])

for a in D:
    ans=-1
    for b in A:
        if(b["x"]-b["t"] <a and a<= b["x"]-b["s"]):
            ans=b["x"]
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,Q=LI()
HQ=[]
EVS=[]
for i in range(N):
    S,T,X=LI()
    EVS.append((S-0.5-X, 1, X))
    EVS.append((T-0.5-X, 0, X))
for i in range(Q):
    D=II()
    EVS.append((D, 2, D))
EVS.sort()

st=set()
PQ=[]
for time, ev, loc in EVS:
    if ev == 1:
        heapq.heappush(PQ, loc)
        st.add(loc)
    elif ev == 0:
        st.remove(loc)
    else:
        while PQ and PQ[0] not in st:
            heapq.heappop(PQ)
        if PQ:
            print(PQ[0])
        else:
            print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,Q=LI()
HQ=[]
EVS=[]
for i in range(N):
    S,T,X=LI()
    EVS.append((S-0.5-X, 1, X))
    EVS.append((T-0.5-X, 0, X))
for i in range(Q):
    D=II()
    EVS.append((D, 2, D))
EVS.sort()

st=set()
PQ=[]
for time, ev, loc in EVS:
    if ev == 1:
        heapq.heappush(PQ, loc)
        st.add(loc)
    elif ev == 0:
        st.remove(loc)
    else:
        while PQ and PQ[0] not in st:
            heapq.heappop(PQ)
        if PQ:
            print(PQ[0])
        else:
            print(-1)