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:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(max(query)+1)

   # for s, t, x in works:
   #     start = s-x if s-x >= 0 else 0
   #     end = t-x if t-x >= 0 else 0
   #     for p in range(start, min(end, len(L))):
   #         L[p] = x
    for q in query:
        print(L[q])


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(max(query)+1)

    for s, t, x in works:
        start = s-x if s-x >= 0 else 0
        end = t-x if t-x >= 0 else 0
        for p in range(start, min(end, len(L))):
            L[p] = x
    for q in query:
        print(L[q])


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(query[-1]+1)

    for s, t, x in works:
        start = max(s-x, 0)
        end = max(t-x, 0)
        for p in range(start, min(end, len(L))):
            L[p] = x
    for q in query:
        print(L[q])


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(query[-1]+1)

    for s, t, x in works:
        start = max(s-x, 0)
        end = max(t-x, 0)
        for p in range(start, min(end, len(L))):
            if L[p] == -1:
                L[p] = x
            else:
                L[p] = min(L[p], x)
    for q in query:
        print(L[q])


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(query[-1]+1)

    for s, t, x in works:
        for p in range(max(s-x, 0), min(max(t-x, 0), query[-1])+1):
            try:
                if L[p] == -1:
                    L[p] = x
                else:
                    L[p] = min(L[p], x)
            except IndexError:
                print(0)
    for q in query:
        print(L[q])


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(query[-1]+1)

    for s, t, x in works:
        for p in range(max(s-x, 0), min(max(t-x, 0), query[-1])+1):
            if L[p] == -1:
                L[p] = x
            else:
                L[p] = min(L[p], x)


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(query[-1]+1)

    for s, t, x in works:
        for p in range(max(s-x, 0), min(max(t-x, 0), query[-1])):
            if L[p] == -1:
                L[p] = x
            else:
                L[p] = min(L[p], x)
    for q in query:
        print(L[q])


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(query[-1]+1)

    for s, t, x in works:
        for p in range(max(s-x, 0), min(max(t-x, 0), query[-1]+1)):
            if L[p] == -1:
                L[p] = x
            else:
                L[p] = min(L[p], x)
    for q in query:
        print(L[q])


solve()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    N, Q = map(int, input().split())
    works = [list(map(int, input().split())) for _ in range(N)]
    query = [int(input()) for _ in range(Q)]

    L = [-1]*(query[-1]+1)

    for s, t, x in works:
        for p in range(max(s-x, 0), max(t-x, 0)):
            if L[p] == -1:
                L[p] = x
            else:
                L[p] = min(L[p], x)
    for q in query:
        print(L[q])


solve()

Submission status: Runtime Error

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 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())
import bisect
 
def main():
  n, q = LI()
  ds = []
  stx = []
  ans = [-1 for i in range(q)]
  stxappend = stx.append
  dsappend = ds.append
  for i in range(n):
      stxappend(LI())
  for i in range(q):
      dsappend(II())
  stx = sorted(stx, key=lambda x: x[2])
  for s, t, x in stx:
      i1 = bisect.bisect_left(ds, s - x)
      i2 = bisect.bisect_left(ds, t - x)
      while i1 < i2
          if ans[i1] == -1:
              ans[i1] = x
          i1 += 1
  print(*ans, sep='\n')
 
if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

/*
vector.push_back()
vector<int> hoge(3,-1); {-1,-1,-1}
vector<vector<int>> hogehoge(2,vector<int>(2,-1)); {{-1,-1},{-1,-1}} 
cin >>temp;
scanf("%d %d %d",&A,&B,&Q);
sort(a.begin(),a.end());
a.push_back(4000000000000);
a.insert(a.begin(),-1000000000000);
upper_bound(a.begin(),a.end(),x); // list[i] > x のイテレータ取得. *itrで数値化 
*/

int checkpoint_num=0;
void pcheck(){
    cout << "----------------" << endl << checkpoint_num << endl << "----------------" << endl;
    checkpoint_num +=1;
}

template <typename T> void debug(T arr){
    for (auto col:arr){
        cout << col << " ";
    }
    cout <<endl;
}

template <typename T> void debug (T arr, int dim){
    for (auto raw:arr){
        for(auto col:raw){
            cout << col << " ";
        }
        cout << endl;
    }
}

class UnionFind {
    public:
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N+1) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N+1; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};



int main(void){
    int n,q;
    int s,t,x,d;
    scanf("%d %d",&n, &q);
    vector<vector<int>> stx;
    vector<vector<int>> t_space;
    vector<int> D;

    for (int i = 0; i < n; ++i){
      scanf("%d %d %d",&s,&t,&x);
      vector<int> temp = {s,t,x};
      stx.push_back(temp);
    }

    for (int i = 0; i < q; ++i){
        scanf("%d",&d);
        D.push_back(-d);
    }

    sort(stx.begin(),stx.end(),[](const vector<int>& xx, const vector<int>& yy){return xx[2]< yy[2];});
    

    for (int i = 0; i < n; ++i){
        vector<int> temp = {stx[i][2]-stx[i][1],stx[i][2]-stx[i][0]};
        t_space.push_back(temp);
    }
    // cout << "**********" << endl;
    // debug(t_space,2);
    // debug(D);


    for (int i = 0; i < q; ++ i){
        bool flag = true;
        for (int j = 0; j < n; ++ j){
            if (D[i] <= t_space[j][0] || D[i] > t_space[j][1]){
                continue;
            }else{
                cout << stx[j][2] << endl;
                flag = false;
                break;
            }
        }
        if(flag){
            cout << -1 << endl;
        }
    }
};

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    a = [s - x, t - x, x] #イベント
    E.append(a)
E.sort(key = lambda x: x[2])
D = []
for i in range(Q):
    D.append(int(input()))

ans = [-1]*Q
check = [-1]*Q

for e in E:
    l = bs.bisect_left(D, e[0])
    r = bs.bisect_left(D, e[1])
    while l != r:
        if check[l] == -1:  
            ans[l] = e[2]
            check[l] = r
            l += 1
        else:
            l = check[l]
        
[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
#import heapq as hp
#import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    app = [s - x, -1, x] #追加イベント
    rem = [t - x, -2, x] #削除イベント
    E.append(app)
    E.append(rem)
for i in range(Q):
    d = [int(input()), i, -1]
    E.append(d)
E.sort(key = lambda x:x[0])

ans = []
stopX = []

for e in E:
    if e[1] == -1:
        stopX.heappush(e[2])
    elif e[1] == -2:
        stopX.remove(e[2])
    else:
        if len(stopX) != 0:
            ans.append(stopX[0])
        else:
            ans.append(-1)
[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for _ in range(N):
  s, t, x = mi()
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
#……と思っていたけど、0になるイベントが複数あると、集合への出し入れがおかしくなる（0を複数入れたあと複数回だそうとするから、無いキーを出そうとしてしまう）
#時間がマイナスでもコード上全く問題無いんだから、外した！
  Events.append((s-x, 1, x))
  Events.append((t-x, -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=itemgetter(0))
Events = Events[::-1] #降順にする reverseを使うのは、「ひっくり返した状態で」安定じゃないとイベントの入力順がズレてエラーが出るため。reverseを使うと、キーが重複している場合は元の順番を保ってしまう（ひっくり返すと、キーが重複している部分に限っては元の順番と反対になってしまい、「存在しない値を集合からひこうとする」というエラーになる）

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
minstop = 10**9+1
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    a, b, c = nextevent
    if b==1: #座標xが通行止めになる
      nowkeptout.add(c)
      minstop = min(c, minstop)
    else: #座標xの通行止めが解除される
      nowkeptout.remove(c)
      if c==minstop and nowkeptout: minstop = min(nowkeptout)
      elif not nowkeptout: minstop = 10**9+1
    try: nextevent = Events.pop()
    except:
      nextevent = (10**9+1, 1, 1) #要素がなくなったらもう処理が起きないようにする
      break
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(minstop)
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for _ in range(N):
  s, t, x = mi()
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
  Events.append((max(0,s-x), 1, x))
  Events.append((max(0,t-x), -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=itemgetter(0))
Events = Events[::-1] #降順にする reverseを使うのは、「ひっくり返した状態で」安定じゃないとイベントの入力順がズレてエラーが出るため。reverseを使うと、キーが重複している場合は元の順番を保ってしまう（ひっくり返すと、キーが重複している部分に限っては元の順番と反対になってしまい、「存在しない値を集合からひこうとする」というエラーになる）

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
minstop = 10**9+1
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    a, b, c = nextevent
    if b==1: #座標xが通行止めになる
      nowkeptout.add(c)
      minstop = min(c, minstop)
    else: #座標xの通行止めが解除される
      nowkeptout.remove(c)
      if c==minstop and nowkeptout: minstop = min(nowkeptout)
      elif not nowkeptout: minstop = 10**9+1
    try: nextevent = Events.pop()
    except:
      nextevent = (10**9+1, 1, 1) #要素がなくなったらもう処理が起きないようにする
      break
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(minstop)
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for _ in range(N):
  s, t, x = mi()
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
  Events.append((max(0,s-x), 1, x))
  Events.append((max(0,t-x), -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=itemgetter(0))
Events = Events[::-1] #降順にする reverseを使うのは、「ひっくり返した状態で」安定じゃないとイベントの入力順がズレてエラーが出るため。reverseを使うと、キーが重複している場合は元の順番を保ってしまう（ひっくり返すと、キーが重複している部分に限っては元の順番と反対になってしまい、「存在しない値を集合からひこうとする」というエラーになる）

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    a, b, c = nextevent
    if b==1: #座標xが通行止めになる
      nowkeptout.add(c)
    else: #座標xの通行止めが解除される
      nowkeptout.remove(c)
    try: nextevent = Events.pop()
    except:
      nextevent = (10**9+1, 0, 0) #要素がなくなったらもう処理が起きないようにする
      break
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(min(nowkeptout))
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

STXs = [tuple(mi()) for _ in range(N)]

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for s, t, x in STXs:
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
  Events.append((max(0,s-x), 1, x))
  Events.append((max(0,t-x), -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=itemgetter(0))
Events = Events[::-1] #降順にする reverseを使うのは、「ひっくり返した状態で」安定じゃないとイベントの入力順がズレてエラーが出るため。reverseを使うと、キーが重複している場合は元の順番を保ってしまう（ひっくり返すと、キーが重複している部分に限っては元の順番と反対になってしまい、「存在しない値を集合からひこうとする」というエラーになる）

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    a, b, c = nextevent
    if b==1: #座標xが通行止めになる
      nowkeptout.add(c)
    else: #座標xの通行止めが解除される
      nowkeptout.remove(c)
    try: nextevent = Events.pop()
    except:
      nextevent = (10**9+1, 0, 0) #要素がなくなったらもう処理が起きないようにする
      break
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(min(nowkeptout))
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

STXs = [tuple(mi()) for _ in range(N)]

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for s, t, x in STXs:
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
  Events.append([max(0,s-x), 1, x])
  Events.append([max(0,t-x), -1, x])

#イベント配列は「影響を受ける人（の出発時間）」で昇順ソートする
from operator import itemgetter
Events = sorted(Events, key=itemgetter(0))
Events.append((10**9+1,0,0)) #これはwhile文を止めるための番兵的なやつ

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nexteventidx = 0 #次に見るイベントのidxを入れる これがn*2になれば全イベ終了m
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while Events[nexteventidx][0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    a, b, c = Events[nexteventidx]
    if b==1: #座標xが通行止めになる
      nowkeptout.add(c)
    else: #座標xの通行止めが解除される
      nowkeptout.remove(c)
    nexteventidx += 1
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(min(nowkeptout))
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()
Anss = [-1] * N

STXs = [tuple(mi()) for _ in range(N)]
from operator import itemgetter
STXs = sorted(STXs, key=itemgetter(2))

for s, t, x in STXs:
#  print(s,t,x)
  for i in range(s-x,t-x):
    if i>=0 and i<=10**9: #iは今回見ている通行止めにぶつかるDの出発時間なので、0未満は無い
      if Anss[i]==-1: #-1じゃなければもう（より小さい）値が入っているので無視
        Anss[i]==x

for _ in range(Q):
  print(Anss[int(input())])

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

n,m = m()

l = [l() for i in range(n)]
l.sort(key = lambda x:x[2])
ans = [-1]*m
ju = [-1]*m
d = [onem() for i in range(m)]
for s,t,x in l:
    ore = bs.bisect_left(d,s-x)
    o = s.bisect_left(d,t-x)
    while (ore < o):
        k = ju[ore]
        if k == -1:
            ans[ore] = x
            ju[ore] = o
            ore += 1
        else:
            ore = k
for i in range(m):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import bisect
N,Q=map(int,input().split())
STX=[list(map(int,input().split())) for i in range(N)]
STX.sort(key=lambda x:x[2])
ans=[-1]*Q
jump=[-1]*Q
D=[int(input()) for i in range(Q)]
for s,t,x in STX:
    l=bisect.bisect_left(D,s-x)
    r=bisect.bisect_left(D,t-x)
    while(l<r):
        k=jump[l]
        if k==-1:
            ans[l]=x
            jump[l]=r
            l+=1
        else:
            l=jump[k]
for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import heapq as hp
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    app = [s - x, 1, x]
    rem = [t - x, -1, x]
    E.append(app)
    E.append(rem)
D = [int(input()) for i in range(Q)]
E.sort(key = lambda x:x[0])

ans = []
stopX = []

for j in range(len(E)):
    while D[0] < E[j][0]:
        if len(stopX) == 0:
            ans.append(-1)
            hp.heappop(D)
        else:
            ans.append(stopX[0])
            hp.heappop(D)
    if E[j][1] == 1:
        hp.heappush(stopX, E[j][2])
    else:
        index = bs.bisect_left(stopX,E[j][2])
        stopX.pop(index)

while len(ans) != Q:
    ans.append(-1)
[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import heapq as hp
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    app = [s - x, 1, x]
    rem = [t - x, -1, x]
    E.append(app)
    E.append(rem)
E.sort(key = lambda x:x[0])
D = [int(input()) for i in range(Q)]

ans = []
stopX = []

for j in range(len(E)):
    while D[0] < E[j][0]:
        if len(stopX) == 0:
            ans.append(-1)
            hp.heappop(D)
        else:
            ans.append(stopX[0])
            hp.heappop(D)
    if E[j][1] == 1:
        hp.heappush(stopX, E[j][2])
    else:
        index = bs.bisect_left(stopX,E[j][2])
        stopX.pop(index)

while len(ans) != Q:
    ans.append(-1)
[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import heapq as hp
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    app = [s - x, 1, x]
    rem = [t - x, -1, x]
    E.append(app)
    E.append(rem)
E.sort(key = lambda x:x[0])
D = [int(input()) for i in range(Q)]

ans = []
stopX = []

for j in range(len(E)):
    while D[0] < E[j][0]:
        if len(stopX) == 0:
            ans.append(-1)
            hp.heappop(D)
        else:
            ans.append(stopX[0])
            hp.heappop(D)
    if E[j][1] == 1:
        hp.heappush(stopX, E[j][2])
    else:
        index = bs.bisect_left(stopX,E[j][2])
        stopX.pop(index)
[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
st = [0] * n
mx = 0
for i in range(n):
    s, t, x = map(int, input().split())
    mx = max(t-x, mx)
    st[i] = [max(s-x, 0), max(t-x, 0), x]
st = sorted(st, key=lambda x: x[2], reverse=True)
l = [-1] * mx
for s, t, x in st:
    l[s:t] = [x] * (t-s)

for i in range(q):
    d = int(input())
    if d >= mx:
        print(-1)
    else:
        print(l[d])