-
Notifications
You must be signed in to change notification settings - Fork 5
/
ssssss.py
79 lines (76 loc) · 2.41 KB
/
ssssss.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
# Copyright (c) 2021 kamyu. All rights reserved.
#
# Facebook Hacker Cup 2021 Final Round - Problem B. SSSSSS
# https://www.facebook.com/codingcompetitions/hacker-cup/2021/final-round/problems/B
#
# Time: O(NlogN)
# Space: O(N)
#
from heapq import heappush, heappop
def ssssss():
N = input()
A_B = [map(int, raw_input().strip().split()) for _ in xrange(N)]
intervals = []
result = [0]*2
max_idx = -1
for i, (A, B) in enumerate(A_B):
if not A:
if max_idx == -1 or A_B[max_idx][1] < B:
max_idx = i
result[0] += 1
else:
intervals.append((A, 0, i))
intervals.append((B, 1, i))
if max_idx == -1:
return " ".join(map(str, result))
intervals.append((A_B[max_idx][1], 1, max_idx))
intervals.sort()
a = b = max_idx
lookup = [False]*N
min_heap = []
for _, t, i in intervals:
if t == 0:
heappush(min_heap, (A_B[i][1], i))
lookup[i] = True
continue
if A_B[a][1] > A_B[b][1]:
a, b = b, a
if lookup[i]:
a = i
lookup[a] = False
result[0] += 1
result[1] += 1
elif i == b:
a, b = b, a
elif i != a: # (not lookup[i]) and (i != a) and (i != b)
continue
assert(a == i)
while min_heap and not lookup[min_heap[0][1]]:
heappop(min_heap)
if min_heap: # a must go to another lowest ladder
a = heappop(min_heap)[1]
lookup[a] = False
result[0] += 1
result[1] += 1
if b != i:
continue
while min_heap and not lookup[min_heap[0][1]]:
heappop(min_heap)
if min_heap: # b must go to another lowest ladder
b = heappop(min_heap)[1]
lookup[b] = False
result[0] += 1
result[1] += 1
else: # b must go to a since there is no other new ladder to go
assert(a != b)
b = a
result[1] += 1
elif a != b: # a must go to b since there is no other new ladder to go
a = b
result[1] += 1
else: # (not min_heap) and (a == b) => no ladder to go
break
assert(a == b)
return " ".join(map(str, result))
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, ssssss())