Contest Duration: - (local time) (180 minutes) Back to Home

Submission #7993108

Source Code Expand

Copy
```import sys

from collections import defaultdict
from heapq import heappush, heappop

# Performance Test

class Treap:

def __init__(self):
self.root = 0
self.left = [0]
self.right = [0]
self.children = [self.left, self.right]
self.key = [0]
self.priority = [0]
self.count = [0]
self.deleted = set()
self.rand = self.xor128()

def xor128(self):
x = 123456789
y = 362436069
z = 521288629
w = 88675123

while True:
t, x, y, z = x ^ ((x << 11) & 0xffffffff), y, z, w
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))
yield w

def get_size(self):
return self.count[self.root]

def _merge(self, li, ri):
left = self.left
right = self.right
children = self.children
priority = self.priority
count = self.count

stack = []
while li != 0 and ri != 0:
if priority[li] > priority[ri]:
stack.append((li, 1))
li = right[li]
else:
stack.append((ri, 0))
ri = left[ri]

vi = li if li != 0 else ri
for pi, d in reversed(stack):
children[d][pi] = vi
count[pi] = count[left[pi]] + count[right[pi]] + 1
vi = pi

return vi

def _split_by_key(self, vi, x):
"""
:return: (LeftRoot, RightRoot)
LeftRoot:  Root node of the split tree consisting of nodes with key < x.
RightNode: Root node of the split tree consisting of nodes with key >= x.
"""
left = self.left
right = self.right
key = self.key
count = self.count

l_stack = []
r_stack = []
while vi != 0:
if x < key[vi]:
r_stack.append(vi)
vi = left[vi]
else:
l_stack.append(vi)
vi = right[vi]

li, ri = 0, 0
for pi in reversed(l_stack):
right[pi] = li
count[pi] = count[left[pi]] + count[li] + 1
li = pi
for pi in reversed(r_stack):
left[pi] = ri
count[pi] = count[ri] + count[right[pi]] + 1
ri = pi

return li, ri

def insert(self, x):
left = self.left
right = self.right
children = self.children
key = self.key
priority = self.priority
count = self.count

np = next(self.rand)

if self.deleted:
ni = self.deleted.pop()
left[ni] = 0
right[ni] = 0
key[ni] = x
priority[ni] = np
count[ni] = 1
else:
ni = len(self.key)
left.append(0)
right.append(0)
key.append(x)
priority.append(np)
count.append(1)

vi = self.root
pi = 0
d = 0

while vi != 0:
if np > priority[vi]:
li, ri = self._split_by_key(vi, x)
left[ni] = li
right[ni] = ri
count[ni] = count[li] + count[ri] + 1
break
pi = vi
d = int(x >= key[vi])
count[vi] += 1
vi = children[d][vi]

if pi == 0:
self.root = ni
else:
children[d][pi] = ni

def delete(self, x):
left = self.left
right = self.right
children = self.children
key = self.key
count = self.count

vi = self.root
pi = 0
d = 0

while vi != 0:
if key[vi] == x:
vi = self._merge(left[vi], right[vi])
break
pi = vi
d = int(x >= key[vi])
count[vi] -= 1
vi = children[d][vi]

if pi == 0:
self.root = vi
else:
children[d][pi] = vi

def upper_bound(self, x):
"""
:return (Node, i)
Node: with the smallest key y satisfying x < y.
i: 0-indexed order.
If same keys exist, return leftmost one.
If not exists, return (None, n).
"""
left = self.left
right = self.right
key = self.key
count = self.count

vi = self.root
ti = 0
i = count[vi]
j = 0
while vi != 0:
if x < key[vi]:
ti = vi
i = j + count[left[vi]]
vi = left[vi]
else:
j += count[left[vi]] + 1
vi = right[vi]
return ti, i

def lower_bound(self, x):
"""
:return (Node, i)
Node: with the smallest key y satisfying x <= y.
i: 0-indexed order.
If same keys exist, return leftmost one.
If not exists, return (None, n).
"""
left = self.left
right = self.right
key = self.key
count = self.count

vi = self.root
ti = 0
i = count[vi]
j = 0
while vi != 0:
if x <= key[vi]:
ti = vi
i = j + count[left[vi]]
vi = left[vi]
else:
j += count[left[vi]] + 1
vi = right[vi]
return ti, i

def get_by_index(self, i):
"""
:return (0-indexed) i-th smallest node.
If i is greater than length, None will be returned.
"""
left = self.left
right = self.right
count = self.count

if i < 0 or self.get_size() <= i:
return 0
vi = self.root
j = i
while vi != 0:
l_cnt = count[left[vi]]
if l_cnt == j:
return vi
if j < l_cnt:
vi = left[vi]
else:
j -= l_cnt + 1
vi = right[vi]

assert False, 'Unreachable'

def get_max(self):
# 多くの場合において処理が単純な分 get_by_index(get_size - 1) より速いが、
# テストケースによっては途中で処理を打ち切れる get_by_index の方が速いことがある
right = self.right
vi = self.root
if vi == 0:
return 0
while right[vi] != 0:
vi = right[vi]
return vi

def get_next(self, i, vi):
"""
:return: next node of i-th "node". (= (i+1)th node)
"""
# If node has right child, the root-node search can be omitted.
# Otherwise, get_by_index(i+1).
left = self.left
right = self.right

if vi == 0:
return 0
if right[vi] == 0:
return self.get_by_index(i + 1)
vi = right[vi]
while left[vi] != 0:
vi = left[vi]
return vi

def get_prev(self, i, vi):
left = self.left
right = self.right

if vi == 0:
return 0
if left[vi] == 0:
return self.get_by_index(i - 1)
vi = left[vi]
while right[vi] != 0:
vi = right[vi]
return vi

def debug_print(self):
self._debug_print(self.root, 0)

def _debug_print(self, vi, depth):
if vi != 0:
self._debug_print(self.left[vi], depth + 1)
print('      ' * depth, self.key[vi], self.priority[vi], self.count[vi])
self._debug_print(self.right[vi], depth + 1)

def dist_insert(x):
heappush(dists, x)
available_dists[x] += 1

def dist_delete(x):
available_dists[x] -= 1

def dist_get_min():
while dists and available_dists[dists[0]] == 0:
heappop(dists)
if dists:
return dists[0]
return 0xffffffff

n, l, x = map(int, input().split())
aaa = list(map(int, sys.stdin))

trp1 = Treap()
dists = []
available_dists = defaultdict(lambda: 0)
trp1key = trp1.key
strawberry = {x}
trp1.insert(min(x, l - x))

buf = []
for a in aaa:
b = min(a, l - a)
if a in strawberry:
vi, i = trp1.lower_bound(b)
li1 = trp1.get_prev(i, vi)
li2 = trp1.get_prev(i - 1, li1)
ri1 = trp1.get_next(i, vi)
ri2 = trp1.get_next(i + 1, ri1)
l1, l2, r1, r2 = trp1key[li1], trp1key[li2], trp1key[ri1], trp1key[ri2]
if li2 != 0:
dist_delete(b - l2)
if ri1 != 0:
dist_insert(r1 - l2)
if ri2 != 0:
dist_delete(r2 - b)
if li1 != 0:
dist_insert(r2 - l1)
if li1 != 0 and ri1 != 0:
dist_delete(r1 - l1)
strawberry.remove(a)
trp1.delete(b)
else:
trp1.insert(b)
vi, i = trp1.lower_bound(b)
li1 = trp1.get_prev(i, vi)
li2 = trp1.get_prev(i - 1, li1)
ri1 = trp1.get_next(i, vi)
ri2 = trp1.get_next(i + 1, ri1)
l1, l2, r1, r2 = trp1key[li1], trp1key[li2], trp1key[ri1], trp1key[ri2]
if li2 != 0:
dist_insert(b - l2)
if ri1 != 0:
dist_delete(r1 - l2)
if ri2 != 0:
dist_insert(r2 - b)
if li1 != 0:
dist_delete(r2 - l1)
if li1 != 0 and ri1 != 0:
dist_insert(r1 - l1)

size = trp1.get_size()
ci2 = trp1.get_by_index(size - 1)
ci1 = trp1.get_prev(size - 1, ci2)
buf.append(min(dist_get_min(), l - trp1key[ci1] - trp1key[ci2]))

print(*buf)
```

#### Submission Info

Submission Time 2019-10-17 01:19:40+0900 C - Maximize Minimum ikatakos PyPy3 (2.4.0) 700 9974 Byte AC 3737 ms 183248 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
 AC × 2
 AC × 27
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 168 ms 38512 KB
01-02.txt AC 581 ms 64472 KB
01-03.txt AC 527 ms 59996 KB
01-04.txt AC 537 ms 61144 KB
01-05.txt AC 538 ms 62556 KB
01-06.txt AC 501 ms 60892 KB
01-07.txt AC 517 ms 62680 KB
01-08.txt AC 484 ms 61788 KB
01-09.txt AC 514 ms 63704 KB
01-10.txt AC 516 ms 65496 KB
01-11.txt AC 588 ms 67672 KB
01-12.txt AC 495 ms 63196 KB
01-13.txt AC 576 ms 66524 KB
01-14.txt AC 3467 ms 133460 KB
01-15.txt AC 2370 ms 146132 KB
01-16.txt AC 1919 ms 138452 KB
01-17.txt AC 1972 ms 141392 KB
01-18.txt AC 2005 ms 136912 KB
01-19.txt AC 2196 ms 159060 KB
01-20.txt AC 2211 ms 157528 KB
01-21.txt AC 2136 ms 155860 KB
01-22.txt AC 3376 ms 182352 KB
01-23.txt AC 2703 ms 141652 KB
01-24.txt AC 3413 ms 183248 KB
01-25.txt AC 3737 ms 161360 KB
sample-01.txt AC 170 ms 38256 KB
sample-02.txt AC 167 ms 38256 KB