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

Solution (Python):

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)

Solution (Python):
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()






seg_el=1<<((N+1).bit_length())
SEG=[1<<60]*(2*seg_el)
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=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))

Solution (Python):
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)

Solution (Python):
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


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])




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])

Solution (Python):
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):
        
        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__":
    
    main()

Solution (Python):
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)

Solution (Python):

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


if __name__ == "__main__":
    solve()

Solution (Python):
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):
        
        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 += self.size
        R += self.size + 1
        
        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)

Solution (Python):
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):
        
        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 += self.size
        R += self.size + 1
        
        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)