E. Measuring Traffic

- iknoom1107(최문기)

문제 풀이

최소 1개의 none은 보장이 되고

none x, y이면 그 위치에서 traffic flow의 범위가 [x, y]이고

on x, y이면 새로 들어오는 traffic flow의 범위가 [x, y]이고

off x, y이면 빠져나가는 traffic flow의 범위가 [x, y]입니다.

만약

(none, x1, y1) -> (none, x2, y2)이면 traffic flow의 범위는 [max(x1, x2), min(y1, y2)]이고

(none, x1, y1) -> (on, x2, y2)이면 traffic flow의 범위는 [x1+x2, y1+y2]이고

(none, x1, y1) -> (off, x2, y2)이면 traffic flow의 범위는 [x1-y2, y1-x2] 겠죠.

위 방법으로

[가장 왼쪽 none] -> [N번째]까지 각 mile에서 범위를 갱신하면 N번째 범위가 나오고

[가장 오른쪽 none] -> [1번째]까지 갱신하면 1번째 범위가 나옵니다.

주의할 것은 [가장 오른쪽 none] -> [1번째]는 역방향이기 때문에

정방향에서의 off는 on로, on은 off로 생각해야합니다.

소스 코드 (Python)

N = int(input())
S = list(input().split() for _ in range(N))
s, e = 0, N-1
while S[s][0] != "none": s += 1 # 가장 왼쪽 none
while S[e][0] != "none": e -= 1 # 가장 오른쪽 none

a,b = 0, 1e9
for i in range(e,-1,-1):
	t,x,y = S[i]
	x,y = int(x),int(y)
	if t == "none":
		a = max(a, x); b = min(b, y)
	elif t == "off":
		a += x; b += y
	elif t == "on":
		a -= y; b -= x
	a = max(a,0)
print(a,b)

a,b = 0, 1e9
for i in range(s,N):
	t,x,y = S[i]
	x,y = int(x),int(y)
	if t == "none":
		a = max(a, x); b = min(b, y)
	elif t == "on":
		a += x; b += y
	elif t == "off":
		a -= y; b -= x
	a = max(a,0)
print(a,b)