input = __import__('sys').stdin.readline
MIS = lambda: map(int,input().split())
range = xrange
INF = 10**18
class SegTree:
def __init__(_, n):
_.n = 1
while _.n < n: _.n<<= 1
_.arr = [INF]*(_.n*2)
def update(_, i, val):
i+= _.n; _.arr[i] = val
while i > 1: i//=2; _.arr[i] = min(_.arr[2*i], _.arr[2*i+1])
def query(_, l, r):
a = INF; l+= _.n; r+= _.n+1
while l < r:
if l&1: a = min(a, _.arr[l]); l+= 1
if r&1: r-= 1; a = min(a, _.arr[r])
l>>=1; r>>=1
return a
n, m = MIS()
plat = [tuple(MIS()) for i in range(n)]
C = set()
for l, r, c, cost in plat: C|= {l,r,c}
C = dict(zip(sorted(C), range(len(C))))
plat = [(C[l], C[r], C[c], cost) for l, r, c, cost in plat]
# dpl[i] = "#1 falls to i-th platform"
ST = SegTree(len(C))
dpl = []
for i in range(n):
l, r, c, cost = plat[i]
if l == 0:
dpl.append(cost)
ST.update(c, cost)
continue
val = cost + ST.query(l, r)
dpl.append(val)
ST.update(c, val)
# dpu[i] = "#m falls to i-th platform"
ST = SegTree(len(C))
dpr = []
for i in range(n):
l, r, c, cost = plat[i]
if r == len(C)-1:
dpr.append(cost)
ST.update(c, cost)
continue
val = cost + ST.query(l, r)
dpr.append(val)
ST.update(c, val)
ans = min(dpl[i]+dpr[i]-plat[i][3] for i in range(n))
print(ans if ans < INF else -1)
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
11376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
11376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
11376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
28 ms |
11376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
