Problem:


Score : 600 points

Problem Statement

We have N points numbered 1 to N arranged in a line in this order.

Takahashi decides to make an undirected graph, using these points as the vertices.
In the beginning, the graph has no edge. Takahashi will do M operations to add edges in this graph.
The i-th operation is as follows:

The operation uses integers L_i and R_i between 1 and N (inclusive), and a positive integer C_i. For every pair of integers (s, t) such that L_i \leq s < t \leq R_i, add an edge of length C_i between Vertex s and Vertex t.

The integers L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M are all given as input.

Takahashi wants to solve the shortest path problem in the final graph obtained. Find the length of the shortest path from Vertex 1 to Vertex N in the final graph.

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq L_i < R_i \leq N

1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
L_1 R_1 C_1
:
L_M R_M C_M

Output

Print the length of the shortest path from Vertex 1 to Vertex N in the final graph.
If there is no shortest path, print -1 instead.

Sample Input 1

4 3
1 3 2
2 4 3
1 4 6

Sample Output 1

5

We have an edge of length 2 between Vertex 1 and Vertex 2, and an edge of length 3 between Vertex 2 and Vertex 4, so there is a path of length 5 between Vertex 1 and Vertex 4.

Sample Input 2

4 2
1 2 1
3 4 2

Sample Output 2

-1

Sample Input 3

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3

Sample Output 3

28



Sample input:
4 3
1 3 2
2 4 3
1 4 6


Sample output:
5

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    class SegmentTree:
        def __init__(self, size, default, op = min):
            self.size = 2**size.bit_length()
            self.dat = [default]*(self.size*2)
            self.op = op

        def update(self, i, x):
            i += self.size
            self.dat[i] = x
            while i > 0:
                i >>= 1
                self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

        def add(self, i, x):
            i += self.size
            self.dat[i] = self.op(self.dat[i], x)
            while i > 0:
                i >>= 1
                self.dat[i] = self.op(self.dat[i], x)

        def get(self, a, b = None):
            if b is None:
                b = a + 1
            l, r = a + self.size, b + self.size
            res = None
            while l < r:
                if l & 1:
                    if res is None:
                        res = self.dat[l]
                    else:
                        res = self.op(res, self.dat[l])
                    l += 1

                if r & 1:
                    r -= 1
                    if res is None:
                        res = self.dat[r]
                    else:
                        res = self.op(res, self.dat[r])
                l >>= 1
                r >>= 1
            return res
    n,m = LI()
    v = LIR(m)
    v.sort()
    d = SegmentTree(n,float("inf"))
    d.update(0,0)
    for l,r,c in v:
        l -= 1
        r -= 1
        m = d.get(l,r+1)
        nd = min(d.get(r),m+c)
        d.update(r,nd)
    ans = d.get(n-1)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
m = map(int,read().split())
LRC = zip(m,m,m)

R_to_L = [[] for _ in range(N+1)]
R_to_C = [[] for _ in range(N+1)]

for l,r,c in LRC:
    R_to_L[r].append(l)
    R_to_C[r].append(c)

INF = 10**18

class MinSegTree():
    def __init__(self,N):
        self.Nelem = N
        self.size = 1<<(N.bit_length()) # 葉の要素数
        
    def build(self,raw_data):
        # raw_data は 0-indexed
        INF = 10**18
        self.data = [INF] * (2*self.size)
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
            i >>= 1
    
    def get_value(self,L,R):
        # [L,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        x = 10**18
        while L < R:
            if L&1:
                y = self.data[L]
                if x > y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x > y: x = y
            L >>= 1; R >>= 1
        return x

dp = MinSegTree(N+1)
dp.build([INF]  * (N+1))

dp.update(1,0)

for r in range(2,N+1):
    x = INF
    for l,c in zip(R_to_L[r], R_to_C[r]):
        y = dp.get_value(l,r-1) + c
        if x>y:
            x=y
    dp.update(r,x)
    if r == N:
        answer = x

if answer == INF:
    answer = -1
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
m = map(int,read().split())
LRC = zip(m,m,m)

R_to_L = [[] for _ in range(N+1)]
R_to_C = [[] for _ in range(N+1)]

for l,r,c in LRC:
    R_to_L[r].append(l)
    R_to_C[r].append(c)

INF = 10**18

class MinSegTree():
    def __init__(self,N):
        self.Nelem = N
        self.size = 1<<(N.bit_length()) # 葉の要素数
        
    def build(self,raw_data):
        # raw_data は 0-indexed
        INF = 10**18
        self.data = [INF] * (2*self.size)
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x<y else y
            i >>= 1
    
    def get_value(self,L,R):
        # [L,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        x = 10**18
        while L < R:
            if L&1:
                y = self.data[L]
                if x > y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x > y: x = y
            L >>= 1; R >>= 1
        return x

dp = MinSegTree(N+1)
dp.build([INF]  * (N+1))

dp.update(1,0)

for r in range(2,N+1):
    x = INF
    for l,c in zip(R_to_L[r], R_to_C[r]):
        y = dp.get_value(l,r-1) + c
        if x>y:
            x=y
    dp.update(r,x)
    if r == N:
        answer = x

if answer == INF:
    answer = -1
print(answer)

Submission status: Runtime Error

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from heapq import heappop, heappush
def resolve():
    n, m = map(int, input().split())
    N = 1 << (n - 1).bit_length()
    N2, now = N * 2, N * 3
    E = [[] for _ in range(N * 3 + m)]
    ref = lambda v : v if v < 3 * N else v - N2

    # build range-edge graph
    for i in range(N - 1, 0, -1):
        cl, cr = i << 1, i << 1 | 1
        E[i].append((cl, 0))
        E[i].append((cr, 0))
        E[ref(cl + N2)].append((ref(i + N2), 0))
        E[ref(cr + N2)].append((ref(i + N2), 0))

    # add range-edge
    for _ in range(m):
        u, v, w = map(int, input().split())
        u -= 1
        # lower
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[ref(l + N2)].append((now, w))
                l += 1
            if r & 1:
                r -= 1
                E[ref(r + N2)].append((now, w))
            l >>= 1
            r >>= 1
        # upper
        l, r = u + N, v + N
        while l < r:
            if l & 1:
                E[now].append((l, 0))
                l += 1
            if r & 1:
                r -= 1
                E[now].append((r, 0))
            l >>= 1
            r >>= 1

    # Dijkstra (source : N, termination : N + n - 1)
    dist = [INF] * now
    dist[N] = 0
    heap = [(0, N)]
    while heap:
        d, v = heappop(heap)
        if dist[v] != d:
            continue
        for nv, w in E[v]:
            if dist[nv] > d + w:
                dist[nv] = d + w
                heappush(heap, (d + w, nv))

    ans = dist[N + n - 1]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is Node: return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    sys.setrecursionlimit(10**7)
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    root = None
    for i in range(1,N):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is Node: return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    root = None
    for i in range(1,N):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is Node: return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    root = None
    for i in range(1,N+1):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if i == N: break
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    elif x <= node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is Node: return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    root = None
    for i in range(1,N+1):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if i == N: break
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is Node: return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data == search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    root = None
    for i in range(1,N+1):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if i == N: break
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

class Node:
    def __init__(self,x):
        self.data = x
        self.count = 1
        self.left = None
        self.right = None

def insert(node,x):
    if node is None: return Node(x)
    elif x == node.data:
        node.count += 1
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

def delete_min(node):
    if node.left is Node: return node.right
    node.left = delete_min(node.left)
    return node

def delete(node,x):
    if node:
        if x == node.data:
            if node.count > 1:
                node.count -= 1
                return node
            elif node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data == search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left,x)
        else:
            node.right = delete(node.right,x)
    return node


def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    root = None
    for i in range(1,N+1):
        update = False
        while j < M and p[j][0] == i:
            root = insert(root,d + p[j][2])
            update = True
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            root = delete(root,z)
            update = True
        if i == N: break
        if root == None:
            print(-1)
            return
        if update:
            d = search_min(root)
    print(d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

S = set()
curmin = 10 ** 10  # 現時点での最小値
flag = False  # 更新が必要か

def insert(x):
    global curmin, flag
    S.add(x)
    if x <= curmin:
        curmin = x
        flag = False
    return


def erase(x):
    global curmin, flag
    S.remove(x)
    if x == curmin:
        flag = True
    return


def minimum():
    global curmin, flag
    if flag:
        curmin = min(S)
        flag = False
    return curmin

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]



    N,M = LI()
    p = [LI() for _ in range(M)]

    p.sort()

    r = [[] for _ in range(N+1)]
    d = 0
    j = 0
    for i in range(1,N+1):
        while j < M and p[j][0] == i:
            insert(d + p[j][2])
            r[p[j][1]].append(d + p[j][2])
            j += 1
        for z in r[i]:
            erase(z)
        if i == N: break
        if len(S) == 0:
            print(-1)
            return

        d = minimum()
    print(d)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import Counter
def main():
    n=int(input())
    D=[int(_) for _ in input().split()]
    dc=Counter(D)
    dci=list(dc.items())
    dci.sort()
    mod,ans=998244353,1
    if D[0]!=0 or (D[0]==0 and dci[0][1]>1):
        print(0)
        sys.exit()
    for i in range(len(dci)):
        if dci[i][0]!=i:
            print(0)
            break
        if i>=2:
            ans*=dci[i-1][1]**dci[i][1]%mod
    else:
        print(ans)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

N, M = map(int, input().split())
edge_d = np.array([input().split() for _ in range(M)], dtype=np.int32)
edge_n = np.vstack([np.arange(2, N + 1, dtype=np.int16),
                   np.arange(1, N, dtype=np.int16),
                   np.ones(N - 1, dtype=np.int8)]).T
edge = np.concatenate([edge_d, edge_d[:, [1, 0, 2]], edge_n]).T

matr = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
ans = dijkstra(matr, indices=0)[-1]
if ans == np.inf:
    ans = 0
print(int(ans) - 1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path

N, M = map(int, input().split())
edge_d = np.array([input().split() for _ in range(M)], dtype=np.int32)
edge_n = np.stack([np.arange(2, N + 1, dtype=np.int16),
                   np.arange(1, N, dtype=np.int16),
                   np.ones(N - 1, dtype=np.int8)]).T
edge = np.concatenate([edge_d, edge_d[:, [1, 0, 2]], edge_n]).T

matr = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
ans = shortest_path(matr, indices=0)[-1]
if ans == np.inf:
    ans = 0
print(int(ans) - 1)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    INF = 10 ** 18

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

    G = [[] for _ in range(N + 1)]
    for _ in range(M):
        L, R, C = map(int, input().split())
        G[L].append([C, R])
        G[R].append([C, L])

    for i in range(1, N):
        G[i + 1].append([0, i])

    d = [INF] * (N + 1)

    def dijkstra(s):
        from heapq import heappop. heappush
        d[s] = 0
        pque = []
        heappush(pque, [0, s])
        
        while pque:
            p = heappop(pque)
            v = p[1]
            if d[v] < p[0]:
                continue
            for i in range(len(G[v])):
                e = G[v][i]
                if d[e[1]] > d[v] + e[0]:
                    d[e[1]] = d[v] + e[0]
                    heappush(pque, [d[e[1]], e[1]])

    dijkstra(1)

    print (-1 if d[-1] == INF else d[-1])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

lst = [tuple(map(int, input().split())) for _ in range(M)]
lst.sort(key = lambda x: x[1])
lst.sort(key = lambda x: x[0])

#セグメント木
#次の2つの処理をO(log N)で実施することができる
# s, tが与えられた時、区間[s, t)の最小値を求める
# i, xが与えられた時、a_iの値をxに変更する

INIT = 10 ** 18 #初期値 答えに関係ないもの
MAX_N = 10 ** 5 + 10 #与えられる要素数の最大
# INIT = 100
data = [INIT] * (2 * MAX_N - 1) #MAX_Nで初期化

#ここに機能をもたせる
def func(vl, vr):
    return min(vl, vr)

def init(n_):
    #簡単のため要素数を2のべき乗に
    n = 1
    while n < n_:
        n *= 2
    return n

# N = int(input()) #配列の数
n = init(N)

def update(k, a): #k番目の値をaに変更 0-index
    # B[a] = k
    k += n - 1
    data[k] = a
    while k > 0: #登りながら更新
        k = (k - 1)//2
        data[k] = func(data[k * 2 + 1], data[k * 2 + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return INIT
    if a <= l and r <= b:
        return data[k]
    else:
        vl = query(a, b, k * 2 + 1, l, (l + r)//2)
        vr = query(a, b, k * 2 + 2, (l + r)//2, r)
        return func(vl, vr)

def initialize(A): #リストAを与えて初期化する
    for i, a in enumerate(A):
        data[i + n - 1] = a
        # B[a] = i
    for i in range((2 * n - 3)//2, -1, -1):
        data[i] = func(data[i * 2 + 1], data[i * 2 + 2])

# def index(a): #要素aがもとのどこに保存されているかを返す関数
#     return B[a]

def value(index): #indexが与えられた時、index番目の値を得る
    return data[index + n - 1]

#初期値の入力
D = [INIT] * N
D[0] = 0
# B = dict() #同じ要素がないのが前提 0-index管理
initialize(D)

#クエリの数
# print (lst)
# print (D)
for a, b, c in lst:
    a -= 1
    b -= 1
    tmp = query(a, b)
    if D[b] > tmp + c:
        D[b] = tmp + c
        update(b, tmp + c)
    # print (D)

# print (D)
print (-1 if D[N - 1] == INIT else D[N - 1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

lst = [tuple(map(int, input().split())) for _ in range(M)]
lst.sort(key = lambda x: x[1])
lst.sort(key = lambda x: x[0])

#セグメント木
#次の2つの処理をO(log N)で実施することができる
# s, tが与えられた時、区間[s, t)の最小値を求める
# i, xが与えられた時、a_iの値をxに変更する

INIT = 10 ** 18 #初期値 答えに関係ないもの
MAX_N = 10 ** 5 + 10 #与えられる要素数の最大
# INIT = 100
data = [INIT] * (2 * MAX_N - 1) #MAX_Nで初期化

#ここに機能をもたせる
def func(vl, vr):
    return min(vl, vr)

def init(n_):
    #簡単のため要素数を2のべき乗に
    n = 1
    while n < n_:
        n *= 2
    return n

# N = int(input()) #配列の数
n = init(N)

def update(k, a): #k番目の値をaに変更 0-index
    # B[a] = k
    k += n - 1
    data[k] = a
    while k > 0: #登りながら更新
        k = (k - 1)//2
        data[k] = func(data[k * 2 + 1], data[k * 2 + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return INIT
    if a <= l and r <= b:
        return data[k]
    else:
        vl = query(a, b, k * 2 + 1, l, (l + r)//2)
        vr = query(a, b, k * 2 + 2, (l + r)//2, r)
        return func(vl, vr)

def initialize(A): #リストAを与えて初期化する
    for i, a in enumerate(A):
        data[i + n - 1] = a
        # B[a] = i
    for i in range((2 * n - 3)//2, -1, -1):
        data[i] = func(data[i * 2 + 1], data[i * 2 + 2])

# def index(a): #要素aがもとのどこに保存されているかを返す関数
#     return B[a]

def value(index): #indexが与えられた時、index番目の値を得る
    return data[index + n - 1]

#初期値の入力
D = [INIT] * N
D[0] = 0
# B = dict() #同じ要素がないのが前提 0-index管理
initialize(D)

#クエリの数
# print (lst)
# print (D)
for a, b, c in lst:
    a -= 1
    b -= 1
    tmp = query(a, b)
    if D[b] > tmp + c:
        D[b] = tmp + c
        update(b, tmp + c)
    # print (D)

# print (D)
print (-1 if D[-1] == INIT else D[-1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

lst = [tuple(map(int, input().split())) for _ in range(M)]
lst.sort(key = lambda x: x[1])
lst.sort(key = lambda x: x[0])

#セグメント木
#次の2つの処理をO(log N)で実施することができる
# s, tが与えられた時、区間[s, t)の最小値を求める
# i, xが与えられた時、a_iの値をxに変更する

INIT = 10 ** 18 #初期値 答えに関係ないもの
MAX_N = 10 ** 5 + 10 #与えられる要素数の最大
# INIT = 100
data = [INIT] * (2 * MAX_N - 1) #MAX_Nで初期化

#ここに機能をもたせる
def func(vl, vr):
    return min(vl, vr)

def init(n_):
    #簡単のため要素数を2のべき乗に
    n = 1
    while n < n_:
        n *= 2
    return n

# N = int(input()) #配列の数
n = init(N)

def update(k, a): #k番目の値をaに変更 0-index
    B[a] = k
    k += n - 1
    data[k] = a
    while k > 0: #登りながら更新
        k = (k - 1)//2
        data[k] = func(data[k * 2 + 1], data[k * 2 + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return INIT
    if a <= l and r <= b:
        return data[k]
    else:
        vl = query(a, b, k * 2 + 1, l, (l + r)//2)
        vr = query(a, b, k * 2 + 2, (l + r)//2, r)
        return func(vl, vr)

def initialize(A): #リストAを与えて初期化する
    for i, a in enumerate(A):
        data[i + n - 1] = a
        B[a] = i
    for i in range((2 * n - 3)//2, -1, -1):
        data[i] = func(data[i * 2 + 1], data[i * 2 + 2])

def index(a): #要素aがもとのどこに保存されているかを返す関数
    return B[a]

def value(index): #indexが与えられた時、index番目の値を得る
    return data[index + n - 1]

#初期値の入力
D = [INIT] * N
D[0] = 0
B = dict() #同じ要素がないのが前提 0-index管理
initialize(D)

#クエリの数
# print (lst)
# print (D)
for a, b, c in lst:
    a -= 1
    b -= 1
    tmp = query(a, b)
    if D[b] > tmp + c:
        D[b] = tmp + c
        update(b, tmp + c)
    # print (D)

# print (D)
print (-1 if D[-1] == INIT else D[-1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

lst = [tuple(map(int, input().split())) for _ in range(M)]
lst.sort(key = lambda x: x[1])
lst.sort(key = lambda x: x[0])

#セグメント木
#次の2つの処理をO(log N)で実施することができる
# s, tが与えられた時、区間[s, t)の最小値を求める
# i, xが与えられた時、a_iの値をxに変更する

INIT = 10 ** 18 #初期値 答えに関係ないもの
MAX_N = 10 ** 5 + 10 #与えられる要素数の最大
# INIT = 100
data = [INIT] * (2 * MAX_N - 1) #MAX_Nで初期化

#ここに機能をもたせる
def func(vl, vr):
    return min(vl, vr)

def init(n_):
    #簡単のため要素数を2のべき乗に
    n = 1
    while n < n_:
        n *= 2
    return n

# N = int(input()) #配列の数
n = init(N)

def update(k, a): #k番目の値をaに変更 0-index
    B[a] = k
    k += n - 1
    data[k] = a
    while k > 0: #登りながら更新
        k = (k - 1)//2
        data[k] = func(data[k * 2 + 1], data[k * 2 + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return INIT
    if a <= l and r <= b:
        return data[k]
    else:
        vl = query(a, b, k * 2 + 1, l, (l + r)//2)
        vr = query(a, b, k * 2 + 2, (l + r)//2, r)
        return func(vl, vr)

def initialize(A): #リストAを与えて初期化する
    for i, a in enumerate(A):
        data[i + n - 1] = a
        B[a] = i
    for i in range((2 * n - 3)//2, -1, -1):
        data[i] = func(data[i * 2 + 1], data[i * 2 + 2])

def index(a): #要素aがもとのどこに保存されているかを返す関数
    return B[a]

def value(index): #indexが与えられた時、index番目の値を得る
    return data[index + n - 1]

#初期値の入力
D = [INIT] * N
D[0] = 0
B = dict() #同じ要素がないのが前提 0-index管理
initialize(D)

#クエリの数
# print (lst)
# print (D)
for a, b, c in lst:
    a -= 1
    b -= 1
    tmp = query(a, b)
    if D[b] > tmp + c:
        D[b] = tmp + c
        update(b, tmp + c)
    # print (D)

# print (D)
print (-1 if D[-1] == INIT else D[-1])