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: Runtime Error

Solution code:
import random
N,Q = list(map(int, input().split()))

STX = [list(map(int, input().split())) for _ in range(N)]
STX.sort(key=lambda x:x[2])


D = [int(input()) for i in range(Q)]
D_binary = [(d,i) for i,d in enumerate(D)]

#binary tree
class Node(object):
    """Tree node: left and right child + data which can be any object
    """
    def __init__(self, data):
        """Node constructor
        @param data node data object
        """
        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
        """Insert new node with data
        @param data node data object to insert
        """
        if self.data is not None:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def lookup(self, data, parent=None):
        """Lookup node containing data
        @param data node data object to look up
        @param parent node's parent
        @returns node and node's parent if found or None, None
        """
        if data < self.data:
            if self.left is None:
                return None, None
            return self.left.lookup(data, self)
        elif data > self.data:
            if self.right is None:
                return None, None
            return self.right.lookup(data, self)
        else:
            return self, parent

    def lookup_near(self, data, parent=None,route =None):
        """Lookup node containing data
        """
        # def f():
        #     return min(r for r in route if r> data)
        if not route:
            route = []
        route.append(self.data)
        if data < self.data:
            if self.left is None:
                # print(route,self.right)
                return min(r for r in route if r> data)
            return self.left.lookup_near(data, self,route)
        elif data > self.data:
            if self.right is None:
                # print(route,self.left)
                return min(r for r in route if r> data)
            return self.right.lookup_near(data, self,route)
        else:
            return self.data


    def delete(self, data):
        """Delete node containing data
        @param data node's content to delete
        """
        # get node containing data
        node, parent = self.lookup(data)
        if node is not None:
            children_count = node.children_count()
            if children_count == 0:
                # if node has no children, just remove it
                if parent:
                    if parent.left is node:
                        parent.left = None
                    else:
                        parent.right = None
                else:
                    self.data = None
            elif children_count == 1:
                # if node has 1 child
                # replace node by its child
                if node.left:
                    n = node.left
                else:
                    n = node.right
                if parent:
                    if parent.left is node:
                        parent.left = n
                    else:
                        parent.right = n
                else:
                    self.left = n.left
                    self.right = n.right
                    self.data = n.data
            else:
                # if node has 2 children
                # find its successor
                parent = node
                successor = node.right
                while successor.left:
                    parent = successor
                    successor = successor.left
                # replace node data by its successor data
                node.data = successor.data
                # fix successor's parent node child
                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right

    def compare_trees(self, node):
        """Compare 2 trees
        @param node tree to compare
        @returns True if the tree passed is identical to this tree
        """
        if node is None:
            return False
        if self.data != node.data:
            return False
        res = True
        if self.left is None:
            if node.left:
                return False
        else:
            res = self.left.compare_trees(node.left)
        if res is False:
            return False
        if self.right is None:
            if node.right:
                return False
        else:
            res = self.right.compare_trees(node.right)
        return res

    def print_tree(self):
        """Print tree content inorder
        """
        if self.left:
            self.left.print_tree()
        print(self.data, end=" ")
        if self.right:
            self.right.print_tree()

    def tree_data(self):
        """Generator to get the tree nodes data
        """
        # we use a stack to traverse the tree in a non-recursive way
        stack = []
        node = self
        while stack or node:
            if node:
                stack.append(node)
                node = node.left
            else:
                # we are returning so we pop the node and we yield it
                node = stack.pop()
                yield node.data
                node = node.right

    def children_count(self):
        """Return the number of children
        @returns number of children: 0, 1, 2
        """
        cnt = 0
        if self.left:
            cnt += 1
        if self.right:
            cnt += 1
        return cnt

D_shuffle = list(D)
random.shuffle(D_shuffle)
bt = Node(None)
for d in D_shuffle:
    bt.insert(d)

# print(D_shuffle)
from collections import defaultdict
ans = defaultdict(lambda :-1)
for s,t,x in STX:
    sx = s-x
    tx = t-x
    while True:
        v = bt.lookup_near(sx)
        if v < tx:
            bt.delete(v)
            ans[v] = x
        else:
            break
for d in D:
    print(ans[d])

Submission status: Runtime Error

Solution code:
def SI(): return int(input())
from collections import defaultdict
import bisect

n, q = LI()
ss, ts, xs, ds = [], [], [], []
stx = []
ans = [-1 for i in range(q)]
for i in range(n):
    s, t, x = LI()
    stx.append((s, t, x))
for i in range(q):
    d = SI()
    ds.append(d)
stx = sorted(stx, key=lambda x: x[2])
for s, t, x in stx:
    sx = s - x
    tx = t - x
    i1 = bisect.bisect_left(ds, sx)
    i2 = bisect.bisect_left(ds, tx)
    for i in range(i1, i2):
        if ans[i] == -1:
            ans[i] = x
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import numpy as np

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

S = []
T = []
X = []

for i in range(N):
    s, t, x = map(int, input().split())
    S.append(s)
    T.append(t)
    X.append(x)

D = []

for i in range(Q):
    D.append(int(input()))

max_row = max(T)
max_col = max(X)

map = np.zeros((max_row+1, max_col+1))

for i in range(N):
    for j in range(S[i], T[i]):
        map[j][X[i]] = 1

for d in D:
    x = d
    mugen = True
    for y in range(max_col+1):
        if map[x][y] > 0:
            print(y)
            mugen = False
            break
        map[x][y] = -5
        x += 1
        if x > max_row:
            break
    if mugen:
        print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

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

S = []
T = []
X = []

for i in range(N):
    s, t, x = map(int, input().split())
    S.append(s)
    T.append(t)
    X.append(x)

D = []

for i in range(Q):
    D.append(int(input()))

max_row = max(max(T), max(D))
max_col = max(X)

map = np.zeros((max_row+1, max_col+1))

for i in range(N):
    for j in range(S[i], T[i]):
        map[j][X[i]] = 1

for d in D:
    x = d
    mugen = True
    for y in range(max_col+1):
        if map[x][y] > 0:
            print(y)
            mugen = False
            break
        map[x][y] = -5
        x += 1
        if x > max_row:
            break
    if mugen:
        print(-1)

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
road = [list(map(int,input().split())) for _ in range(N)]
start = [int(input()) for _ in range(Q)]

#工事の情報からどの時刻にスタートすると自分の工事に引っかかるかを求めておく

#xの小さいものからソート
road.sort(key=lambda x:-x[2])
NG_start_info = []
for line in road:
    #半開区間
    NG_start_info.append([line[0]-line[2],line[1]-line[2],line[2]])
# print(NG_start_info)

#時刻は0始まり
info = [-1]*(start[-1]+1)
for line in NG_start_info:
    if line[1] >= 1:
        if line[0] >= 0:
            info[line[0]:line[1]] = [line[2]]*(line[1]-line[0])
        else:
            info[:line[1]] = [line[2]]*(line[1])

for person in start:
    print(info[person])

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
road = [list(map(int,input().split())) for _ in range(N)]
start = [int(input()) for _ in range(Q)]

#工事の情報からどの時刻にスタートすると自分の工事に引っかかるかを求めておく

#xの小さいものからソート
road.sort(key=lambda x:-x[2])
NG_start_info = []
for line in road:
    #半開区間
    NG_start_info.append([line[0]-line[2],line[1]-line[2],line[2]])
# print(NG_start_info)

#時刻は0始まり
info = [-1]*(start[-1]+1)
for line in NG_start_info:
    if line[0] >= 0:
        info[line[0]:line[1]] = [line[2]]*(line[1]-line[0])
    else:
        info[:line[1]] = [line[2]]*(line[1])

for person in start:
    print(info[person])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

struct Work {
	int s, t, x, i;
	Work(int s, int t, int x, int i) : s(s - x), t(t - x), x(x), i(i) {}
	void print() {
		printf("s: %d, t: %d, x: %d, i: %d\n", s, t, x, i);	
	}
};

bool cmp(Work w1, Work w2) {
	return w1.s < w2.s;
}

int main() {
	freopen("1.in", "r", stdin);
	int n, q;
	scanf("%d %d", &n, &q);
	vector<Work> work;
	for (int i = 0; i < n; i++) {
		int s, t, x;
		cin >> s >> t >> x;
		work.push_back(Work(s, t, x, i));
	}
	sort(work.begin(), work.end(), cmp);
	// for (int i = 0; i < n; i++) {
	// 	work[i].print();
	// }
	int now = 0;
	vector<pair<int, int>> t;
	set<pair<int, int>> x;
	while (q--) {
		int d;
		cin >> d;
		// cout << "Doing: " << d << endl;
		while (t.size() && t[0].first <= d) {
			x.erase(make_pair(work[t[0].second].x, work[t[0].second].i));
			pop_heap(t.begin(), t.end(), greater<pair<int, int>>());
			t.pop_back();
		}
		while (now < n && work[now].s <= d) {
			if (work[now].t > d) {
				// cout << "In: " << now << endl;
				x.insert(make_pair(work[now].x, work[now].i));
				t.push_back(make_pair(work[now].t, now));
				push_heap(t.begin(), t.end(), greater<pair<int, int>>());
			}
			now++;
		}
		if (x.size()) {
			cout << x.begin() -> first << endl;
		} else {
			cout << "-1" << endl;
		}
	}
	return 0;
}

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left, bisect_right


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = [int(line) for line in lines[n:]]
rut = RangeUpdateTree(q)
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
data = rut.data[rut.offset:]
# rut.debug_print()
print('\n'.join(map(str, data[:q])))

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left, bisect_right


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = [int(line) for line in lines[n:]]
rut = RangeUpdateTree(q * 2)
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
data = rut.data[rut.offset:]
# rut.debug_print()
print('\n'.join(map(str, data[:q])))

Submission status: Runtime Error

Solution code:
import sys


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = [int(line) for line in lines[n:]]
max_d = ddd[-1]
rut = RangeUpdateTree(max_d + 1)
for x, s, t in kkk:
    ss = max(0, s - x)
    tt = min(max_d + 1, t - x)
    rut.update(ss, tt, x)
data = rut.data[rut.offset:]
print('\n'.join(map(str, (data[d] for d in ddd))))