GBC

뭐가 문제인건지..

기본 TC는 통과.....흠..

N log (N) 알고리즘으로 구현하지 말고 그냥 NM으로 구현할까? 귀찮...

import sys
import bisect

limits = []
test = []

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

for i in range(N):
    limits += tuple(map(int, sys.stdin.readline().split())),

for i in range(M):
    test += tuple(map(int, sys.stdin.readline().split())),


tbl = [(0, 0)]
start = 1

for length, speed in limits:
    tbl += (start + length - 1, speed),
    start += length

valid = []
start = 1
for length, speed in test:
    valid += (start, start + length - 1, speed),
    start += length

def search(vals, target):
    l = 0
    r = len(vals) - 1

    while l <= r:
        m = (l + r)//2
        if vals[m][0] == target:
            return m

        if vals[m][0] < target:
            l = m + 1
        else:
            r = m - 1

    return l

mx = 0
for start, end, speed in valid:
    for target in [start, end]:
        idx = search(tbl, target)
        diff = speed - tbl[idx][1]
        mx = max(mx, diff)

print(mx)