• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 21st, 2020 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. SM
2.
3. from typing import List, Any
4.
5.
6. def sift_up(heap: List[Any], pos: int) -> None:
7.     par = (pos - 1) // 2
8.     while par >= 0:
9.         if heap[par] < heap[pos]:
10.             heap[par], heap[pos] = heap[pos], heap[par]
11.         else:
12.             return None
13.         pos, par = par, (par - 1) // 2
14.
15.
16. def sift_down(heap: List[Any], length: int) -> None:
17.     pos = 0
18.     while pos * 2 + 1 < length:
19.         if pos * 2 + 2 < length and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
20.             child = pos * 2 + 2
21.         else:
22.             child = pos * 2 + 1
23.         if heap[child] > heap[pos]:
24.             heap[child], heap[pos] = heap[pos], heap[child]
25.         pos = child
26.
27.
28. def heap_sort(arr: List[Any]) -> List[Any]:
29.     heap = []
30.     for i in range(len(arr)):
31.         heap.append(arr[i])
32.         sift_up(heap, i - 1)
33.     heap_len = len(heap)
34.     while heap_len > 1:
35.         if heap[heap_len - 1] < heap[0]:
36.             heap[heap_len - 1], heap[0] = heap[0], heap[heap_len - 1]
37.         heap_len -= 1
38.         sift_down(heap, heap_len)
39.     return heap
40.
41.
42. A = list(map(int, input().split()))
43. print(' '.join(map(str, heap_sort(A))))
44.
45.
46. SN
47.
48. from typing import List, Any
49.
50.
51. def sift_up(heap: List[Any], pos: int) -> int:
52.     par = (pos - 1) // 2
53.     while par >= 0:
54.         if heap[par] < heap[pos]:
55.             heap[par], heap[pos] = heap[pos], heap[par]
56.         else:
57.             return pos
58.         pos, par = par, (par - 1) // 2
59.     return pos
60.
61.
62. def sift_down(heap: List[Any], length: int) -> None:
63.     pos = 0
64.     while pos * 2 + 1 < length:
65.         if pos * 2 + 2 < length and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
66.             child = pos * 2 + 2
67.         else:
68.             child = pos * 2 + 1
69.         if heap[child] > heap[pos]:
70.             heap[child], heap[pos] = heap[pos], heap[child]
71.         pos = child
72.
73.
74. n = int(input())
75. A = list(map(int, input().split()))
76. for j in range(int(input())):
77.     i, x = map(int, input().split())
78.     A[i] += x
79.     print(sift_up(A, i))
80. print(' '.join(map(str, A)))
81.
82.
83. SO
84.
85. from typing import List, Any
86.
87.
88. def sift_up(heap: List[Any], pos: int) -> int:
89.     par = (pos - 1) // 2
90.     while par >= 0:
91.         if heap[par] < heap[pos]:
92.             heap[par], heap[pos] = heap[pos], heap[par]
93.         else:
94.             return pos
95.         pos, par = par, (par - 1) // 2
96.     return pos
97.
98.
99. def sift_down(heap: List[Any], pos: int) -> int:
100.     ans = pos
101.     while pos * 2 + 1 < len(heap):
102.         if pos * 2 + 2 < len(heap) and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
103.             child = pos * 2 + 2
104.         else:
105.             child = pos * 2 + 1
106.         if heap[child] > heap[pos]:
107.             heap[child], heap[pos] = heap[pos], heap[child]
108.             ans = child
109.         pos = child
110.     return ans
111.
112.
113. n = int(input())
114. A = list(map(int, input().split()))
115. for j in range(int(input())):
116.     i, x = map(int, input().split())
117.     A[i] -= x
118.     print(sift_down(A, i))
119. print(' '.join(map(str, A)))
120.
121. SP
122.
123.
124. from typing import List, Any
125.
126.
127. def sift_up(heap: List[Any], pos: int) -> int:
128.     par = (pos - 1) // 2
129.     while par >= 0:
130.         if heap[par] < heap[pos]:
131.             heap[par], heap[pos] = heap[pos], heap[par]
132.         else:
133.             return pos
134.         pos, par = par, (par - 1) // 2
135.     return pos
136.
137.
138. def sift_down(heap: List[Any]) -> int:
139.     ans = pos = 0
140.     while pos * 2 + 1 < len(heap):
141.         if pos * 2 + 2 < len(heap) and heap[pos * 2 + 2] > heap[pos * 2 + 1]:
142.             child = pos * 2 + 2
143.         else:
144.             child = pos * 2 + 1
145.         if heap[child] > heap[pos]:
146.             heap[child], heap[pos] = heap[pos], heap[child]
147.             ans = child
148.         pos = child
149.     return ans
150.
151.
152. def insert(heap: List[int], x: int) -> int:
153.     if len(heap) == n:
154.         return -1
155.     heap.append(x)
156.     return sift_up(heap, len(heap) - 1)
157.
158.
159. def extract(heap: List[int]) -> List[Any]:
160.     if len(heap):
161.         heap[-1], heap[0] = heap[0], heap[-1]
162.         ans = heap.pop()
163.         return [sift_down(heap), ans]
164.     return [-1]
165.
166.
167. n, m = map(int, input().split())
168. queue = []  # type: List[int]
169. for j in range(m):
170.     r = list(map(int, input().split()))
171.     if r[0] == 1:
172.         print(*extract(queue))
173.     else:
174.         print(insert(queue, r[1]))
175. print(' '.join(map(str, queue)))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top