oj.uz

Submission #113008

# Submission time Handle Problem Language Result Execution time Memory
113008 2019-05-23T04:05:20 Z jh05013 Pinball (JOI14_pinball) PyPy
0 / 100
 30 ms 11248 KB 
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
        if _.arr[i] < val: return
        _.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)

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11248 KB Output is correct
2 Correct 29 ms 11240 KB Output is correct
3 Correct 28 ms 11248 KB Output is correct
4 Correct 29 ms 11240 KB Output is correct
5 Correct 27 ms 11240 KB Output is correct
6 Correct 27 ms 11240 KB Output is correct
7 Incorrect 30 ms 11240 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11248 KB Output is correct
2 Correct 29 ms 11240 KB Output is correct
3 Correct 28 ms 11248 KB Output is correct
4 Correct 29 ms 11240 KB Output is correct
5 Correct 27 ms 11240 KB Output is correct
6 Correct 27 ms 11240 KB Output is correct
7 Incorrect 30 ms 11240 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11248 KB Output is correct
2 Correct 29 ms 11240 KB Output is correct
3 Correct 28 ms 11248 KB Output is correct
4 Correct 29 ms 11240 KB Output is correct
5 Correct 27 ms 11240 KB Output is correct
6 Correct 27 ms 11240 KB Output is correct
7 Incorrect 30 ms 11240 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11248 KB Output is correct
2 Correct 29 ms 11240 KB Output is correct
3 Correct 28 ms 11248 KB Output is correct
4 Correct 29 ms 11240 KB Output is correct
5 Correct 27 ms 11240 KB Output is correct
6 Correct 27 ms 11240 KB Output is correct
7 Incorrect 30 ms 11240 KB Output isn't correct
8 Halted 0 ms 0 KB -