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


class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


N, C = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(C)]
L = sorted(L, key=lambda x: (x[1], -x[2], x[0]), reverse=True)

Seg = SegmentTree(N+1, func=lambda a, b: min(a, b))
Seg.set(N, 0)
Seg.build()

dist = [float("inf")]*(N+1)
dist[-1] = 0
for l, r, c in L:
    new = min(Seg.query(l, r+1)+c, Seg.query(l, l+1))
    Seg.update(l, new)
ans = Seg.query(1, 2)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        self.n = n
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = min(x, self.tree[i ^ 1])
            i >>= 1

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        # (k, l, r)
        # k   : 現在調べている区間のtree内index
        # l, r: kが表す区間の左右端index [l, r)
        q = [(1, 0, self.n2)]

        while q:
            k, l, r = q.pop()

            if a <= l and r <= b:
                result = min(result, self.tree[k])
                continue

            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))

        return result

N,M = map(int,input().split())
edges = [list(map(int,input().split())) for i in range(M)]
edges.sort()

ST = SegTreeMin(N+1,10**15)
ST.update(0,0)

for i in range(M):
    min_ = ST.get_min(edges[i][0]-1,edges[i][1]-1)
    if min_+edges[i][2] < ST.get_min(edges[i][1]-1,edges[i][1]):
        ST.update(edges[i][1]-1,min_+edges[i][2])
if ST.get_min(N-1,N)!=10**15:
    print(ST.get_min(N-1,N))
else:print(-1)

Submission status: Accepted

Solution code:
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n,m = map(int,input().split())

edge = [[] for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1]) 
for i in range(1,n):
  edge[i].append([0,i-1])
x=dijkstra_heap(0)[n-1]
if x==float("inf"):
  print(-1)
else:
  print(x)

Submission status: Accepted

Solution code:
from collections import deque
import heapq

N,M = map(int,input().split())
LRC2 = []

for i in range(M):
    
    L,R,C = map(int,input().split())
    L -= 1
    R -= 1
    LRC2.append([L,R,C])

LRC2.sort()

LRC = deque([])

for i in LRC2:
    LRC.append(i)

q = []

for i in range(N):

    while len(LRC) > 0 and LRC[0][0] == i:
        now = LRC.popleft()
        L = now[0]
        C = now[2]
        R = now[1]

        if L == 0:
            heapq.heappush(q,[C,R])
            continue

        while len(q) > 0 and q[0][1] < i:
            heapq.heappop(q)

        if len(q) > 0:
            heapq.heappush(q,[C + q[0][0] , R])

    #print (LRC,q)


while len(q) > 0 and q[0][1] < N-1:
    heapq.heappop(q)

#print (q)

if len(q) > 0:
    print (q[0][0])

else:
    print (-1)

Submission status: Accepted

Solution code:

"""
演算子は要素とセットでモノイドを形成するようなものでなければならない。
すなわち、結合律が成り立ち単位元が存在する必要がある。

equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
"""
class SegmentTree:

    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

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

memo = sorted(tuple(map(int,input().split())) for _ in range(M))

seg = SegmentTree.all_identity(min, None, float('inf'), N)

seg[0] = 0

for l,r,c in memo:
    seg[r-1] = min(seg[r-1], seg[l-1:r] + c)

res = seg[N-1]
print(res if res != float('inf') else -1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Aug  4 22:01:34 2019

@author: miz18
"""




class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = min(x,self.node[k])
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res


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

road = []
for i in range(M):
    road.append(list(map(int,input().split())))

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

R = [10**27]*N
R[0] = 0
ST = SegmentTree(R,min,10**27)

for i in range(M):
    now_min = ST.get(road[i][0]-1,road[i][1]-1)
    ST.substitute(road[i][1]-1,now_min+road[i][2])
ans  = ST.get_one(N-1)

if ans>=10**27:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist


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

dist = dijkstra(adj, 1)
# print(adj)
if dist[N] < 10**20:
    print(dist[N])
else:
    print(-1)

Submission status: Accepted

Solution code:
class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: i番目をvalに変更する
    get_min: 区間[begin, end)の最小値を求める
    """
    def __init__(self, n):
        self.n = n
        self.INF = 10**18
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = min(self.node[2*i + 1], self.node[2*i + 2])

    def get_min(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = min(s, self.node[end])
            if (begin - 1) & 1:
                s = min(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s


from operator import itemgetter


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

info = sorted(info, key = itemgetter(1))
st = SegmentTree(n)
st.update(0, 0)

i = 0
for num in range(n+1):
    while True:
        if i >= m:
            break
        if info[i][1] != num:
            break
        else:
            l = info[i][0] - 1
            r = num
            tmp = min(st.get_min(l, r) + info[i][2], st.get_min(num - 1, num))
            st.update(num-1, tmp)
            i += 1
ans = st.get_min(n-1, n)
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
inf = float('inf')

n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]

a.sort(key=itemgetter(2))
a.sort(key=itemgetter(1))
a.sort(key=itemgetter(0))

d = [inf]*(n+1)
d[1]=0
for i in range(m):
    l,r,c = a[i]
    if d[l]==inf:
        print(-1)
        exit()
    for j in range(r-l):
        if d[r-j]>d[l]+c:
            d[r-j]=d[l]+c
        else:
            break
print(d[n]if d[n]!=inf else -1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys

n,m = list(map(int,input().split()))

pl = []
for _ in range(m):
    l,r,c = list(map(int,input().split()))
    pl.append((l-1,r-1,c))

dp = [float('inf') for i in range(n)]
dp[0] = 0
pl = sorted(pl)

for l,r,c in pl:
    for rr in range(r,l,-1):
        if dp[rr] > dp[l] + c:
            dp[rr] = dp[l] + c
        else:
            break

if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import heapq
import sys
N, M = map(int, input().split())
edges = []
for _ in range(M):
    l, r, c = map(int, input().split())
    edges.append((l-1, r-1, c))
edges.sort(reverse = True)
dp = [0]*N
que = [(0, 0)]
for i in range(1, N):
    while len(edges)>0 and edges[-1][0] == i-1:
        e = edges.pop()
        heapq.heappush(que, (dp[i-1]+e[2], e[1]))
    while True:
        if len(que) == 0:
            print(-1)
            sys.exit()
        e = heapq.heappop(que)
        if e[1]>=i:
            dp[i] = e[0]
            heapq.heappush(que, e)
            break
print(dp[-1])

Submission status: Accepted

Solution code:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


class Node:
    def __init__(self,value,index):
        self.value = value
        self.index = index

    def __str__(self):
        return 'val : ' + str(self.value) + ' index : ' + str(self.index)

# 0-indexed SegmentTree
class SegmentTree:
    def __init__(self,N,default_list,default_value=INF):
        self.N0 = pow(2,(N-1).bit_length())
        self.nodes = [Node(default_value,i+1-self.N0) for i in range(2*self.N0-1)]
        for i in reversed(range(2*self.N0-1)):
            ind = i+1-self.N0
            if ind >= N:
                self.nodes[i].value = default_value
            elif N > ind >= 0:
                self.nodes[i].value = default_list[ind]
            else:
                self.nodes[i] = self.process(self.nodes[i*2+1],self.nodes[i*2+2])

    def __getitem__(self,key): # getiten : ST[i]
        return self.nodes[key+self.N0-1].value

    def __setitem__(self,i,x): # update : ST[i] = x
        i += self.N0 - 1
        self.nodes[i].value = x
        while i > 0:
            i = (i-1)//2
            self.nodes[i] = self.process(self.nodes[i*2+1],self.nodes[i*2+2])

    def __str__(self):
        return '['+', '.join(map(str,[self.nodes[i+self.N0-1].value for i in range(self.N0)]))+']'

    def query(self,L,R): #[L,R)の値
        retnode = Node(INF,INF)
        L += self.N0
        R += self.N0
        while L < R:
            if R&1 :
                R -= 1
                retnode = self.process(retnode,self.nodes[R-1])
            if L&1 :
                retnode = self.process(retnode,self.nodes[L-1])
                L += 1
            L >>= 1; R >>= 1
        return retnode

    def process(self,node_x,node_y): #x,yが子の時，親に返る値
        if node_x.value < node_y.value:
            return node_x
        else:
            return node_y


N,M = inpl()

ST = SegmentTree(N,[INF]*N)
ST[0] = 0

LRc = []
for _ in range(M):
    L,R,c = inpl()
    LRc.append((L-1,R-1,c))

LRc.sort()

for L,R,c in LRc:
    MIN = ST.query(L,R+1).value
    if ST[R] > MIN + c:
        ST[R] = MIN + c

if ST[N-1] == INF:
    print(-1)
else:
    print(ST[N-1])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
import heapq
# import math
INF = 10**11

def main():
    n, m= getList()
    begin = [[] for i in range(n)]
    cost = [-1 for i in range(n)]
    for i in range(m):
        st, en, cos = getList()
        begin[st-1].append((cos, en-1))

    h = []
    for warp in begin[0]:
        heapq.heappush(h, warp)
    cur_mas = 0

    while(h):
        cand = heapq.heappop(h)
        if cand[1] > cur_mas:
            # 歩を1つ進め、その場所を更新
            cur_mas += 1
            cost[cur_mas] = cand[0]
            for warp in begin[cur_mas]:
                # そこまでの距離とコストを足す
                tcos, ten = warp[0] + cost[cur_mas], warp[1]
                heapq.heappush(h, (tcos, ten))
            heapq.heappush(h, cand)



    print(cost[n-1])
if __name__ == "__main__":
    main()

Submission status: Accepted

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

n,m = map(int,input().split())

dg = 10**6


edge = [[] for _ in [0]*n]

for _ in [0]*m:
    l,r,c = map(int,input().split())
    edge[l-1].append(c*dg+r-1)

d = [10**20]*n
d[0] = 0

tank = []
for e in edge[0]:
    heapq.heappush(tank,e)
while len(tank) != 0:
    q = heapq.heappop(tank)
    go = q%dg
    if d[go] != 10**20:
        continue
    cost = q//dg

    for i in range(go,-1,-1):
        if d[i] != 10**20:
            break
        d[i] = cost
        for e in edge[i]:
            heapq.heappush(tank,e+cost*dg)
if d[-1] == 10**20:
    print(-1)
else:
    print(d[-1])

Submission status: Accepted

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

INF = 10**18

class RMQ:
    def __init__(self, a):
        self.n = len(a)
        self.size = 2**(self.n - 1).bit_length()
        self.data = [INF] * (2*self.size-1)
        self.initialize(a)

    # Initialize data
    def initialize(self, a):
        for i in range(self.n):
            self.data[self.size + i - 1] = a[i]
        for i in range(self.size-2, -1, -1):
            self.data[i] = min(self.data[i*2 + 1], self.data[i*2 + 2])

    # Update ak as x
    def update(self, k, x):
        k += self.size - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    # Min value in [l, r)
    def query(self, l, r):
        L = l + self.size; R = r + self.size
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n, m = [int(item) for item in input().split()]
dist = [INF] * n
dist[0] = 0
rmq = RMQ(dist)
lrc = []
for i in range(m):
    l, r, c = [int(item) for item in input().split()]
    l -= 1; r -= 1
    lrc.append((l, r, c))
lrc.sort()

for l, r, c in lrc:
    min_dist = rmq.query(l, r+1)
    r_dist = rmq.query(r, r+1)
    if min_dist + c < r_dist:
        rmq.update(r, min_dist+c)

ans = rmq.query(n-1, n)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc014/submissions/3935971
class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]
    def __init__(self, a: list, default: int, op):
        from math import ceil, log
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        self.default = default
        self.op = op
        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

    def get_value(self, x: int, y: int) -> int:  # 半開区間
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1
        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

from operator import itemgetter
N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
LRC.sort(key=itemgetter(0))

idx_LRC = 0
q = []

seg = SegmentTree([float("inf")] * (N+1), float("inf"), min)

seg.set_value(1, 0)
for v in range(1, N+1):
    d = seg.get_value(v, N+1)
    while idx_LRC < M:
        l, r, c = LRC[idx_LRC]
        if l <= v:
            seg.set_value(r, min(seg.tree[r+seg.elem_size], d + c))
            idx_LRC += 1
        else:
            break
ans = seg.tree[N+seg.elem_size]
print(ans if ans!=float("inf") else -1)

Submission status: Accepted

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

N,M=map(int,input().split())
B=[tuple(map(int,input().split())) for i in range(M)]
B.sort()


#Starry sky tree(一点取得、範囲min更新の1-indexed Segment tree. Aは0-indexedなことに注意.



seg_el=1<<((N+1).bit_length())# Segment treeの台の要素数
SEG=[1<<60]*(2*seg_el)# 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
SEG[1+seg_el]=0

def getvalue(n,seg_el):# 一点の値を取得
    i=n+seg_el
    ANS=1<<60
    
    ANS=min(SEG[i],ANS)
    i>>=1# 子ノードへ
    
    while i!=0:
        ANS=min(SEG[i],ANS)
        i>>=1

    return ANS

def updates(l,r,x):# 区間[l,r)のminを更新.
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG[L]=min(x,SEG[L])
            L+=1

        if R & 1:
            R-=1
            SEG[R]=min(x,SEG[R])
        L>>=1
        R>>=1

for l,r,c in B:
    x=getvalue(l,seg_el)
    updates(l,r+1,x+c)

if getvalue(N,seg_el)==1<<60:
    print(-1)
else:
    print(getvalue(N,seg_el))

Submission status: Accepted

Solution code:
import sys
from heapq import heappop as hpp, heappush as hp
inf = 10**20
def dijkstra(N, s, Edge):
    dist = [inf] * N
    Q = [(0, s)]
    decided = set()
    for _ in range(N):
        while True:
            dn, vn = hpp(Q)
            if vn not in decided:
                decided.add(vn)
                dist[vn] = dn
                break
        for vf, df in Edge[vn]:
            if vf not in decided:
                hp(Q, (dn + df, vf))
    return dist

readline = sys.stdin.readline
N, M = map(int, readline().split())

Edge = [[] for _ in range(N)]
for i in range(M):
    L, R, C = map(int, readline().split())
    L -= 1
    R -= 1
    Edge[L].append((R, C))

for i in range(1, N):
    Edge[i].append((i-1, 0))
for i in range(1, N):
    Edge[0].append((i, inf))
dist = dijkstra(N, 0, Edge)
if dist[N-1] == inf:
    ans = -1
else:
    ans = dist[N-1]
print(ans)

Submission status: Accepted

Solution code:
import heapq
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, M = list(map(int, sys.stdin.readline().split()))
LRC = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]


def test():
    LRC.sort()
    dp = [INF] * N
    dp[0] = 0
    for l, r, c in LRC:
        l -= 1
        r -= 1
        for i in range(l, r + 1):
            dp[i] = min(dp[i], dp[l] + c)
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


# test()

heap = []
LRC.sort()
LRC = [(l - 1, r - 1, c) for l, r, c in LRC]
mi = 0
dp = [INF] * N
dp[0] = 0
for pos in range(N):
    if dp[pos] == INF:
        break
    while mi < M and LRC[mi][0] <= pos:
        l, r, c = LRC[mi]
        heapq.heappush(heap, (dp[pos] + c, r))
        mi += 1
    while heap and heap[0][1] <= pos:
        heapq.heappop(heap)
    if not heap:
        break
    dp[pos + 1] = heap[0][0]


if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q-1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res


def solve(n, m, lrc_list):
    s = SegmentTree([10 ** 15 + 1] * n, min, 10 ** 15 + 1)
    s.update(0, 0)
    lrc_list_s = sorted(lrc_list, key=lambda x: x[0])
    for i in range(m):
        l, r, c = lrc_list_s[i]
        p = s.query(l - 1, r)
        if p + c < s.query(r - 1, r):
            s.update(r - 1, p + c)
    if s.query(n - 1, n) == 10 ** 15 + 1:
        return -1
    else:
        return s.query(n - 1, n)


def main():
    n, m = map(int, input().split())
    lrc_list = []
    for _ in range(m):
        l, r, c = map(int, input().split())
        lrc_list.append([l, r, c])
    res = solve(n, m, lrc_list)
    print(res)


def test():
    assert solve(4, 3, [[1, 3, 2], [2, 4, 3], [1, 4, 6]]) == 5
    assert solve(4, 2, [[1, 2, 1], [3, 4, 2]]) == -1


if __name__ == "__main__":
    # test()
    main()

Submission status: Accepted

Solution code:
NN = 17
MI = [1<<100] * ((1<<NN+1)-1)
def update(a, x):
    i = (1<<NN) - 1 + a
    MI[i] = min(MI[i], x)
    while True:
        i = (i-1) // 2
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        if i == 0:
            break

def rangemin(a):
    l = a + (1<<NN)
    r = ((1<<NN+1)-2)
    mi = 1<<100
    while l < r:
        if l%2:
            mi = min(mi, MI[l-1])
            l += 1
        if r%2:
            r -= 1
            mi = min(mi, MI[r-1])
        l >>= 1
        r >>= 1
    return mi

N, M = map(int, input().split())
X = []
for _ in range(M):
    l, r, c = map(int, input().split())
    X.append((l, r, c))

X = sorted(X)
update(1, 0)
for l, r, c in X:
    mi = rangemin(l)
    update(r, mi + c)

ans = MI[(1<<NN) - 1 + N]
print(ans if ans < 1<<100 else -1)