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

Submission #7993208

Source Code Expand

Copy
```import sys

from collections import defaultdict
from heapq import heappush, heappop

# Performance Test

class Treap:
__slots__ = ('root', 'left', 'right', 'children', 'key', 'priority', 'count', 'deleted', 'rand')

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.xor64()

def xor64(self):
x = 88172645463325252

while True:
x = x ^ ((x << 7) & 0xffffffff)
x = x ^ (x >> 9)
yield x

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

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

vi = li if li != 0 else ri
for pi, d in reversed(stack):
self.children[d][pi] = vi
self.count[pi] = self.count[self.left[pi]] + self.count[self.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.
"""
l_stack = []
r_stack = []
while vi != 0:
if x < self.key[vi]:
r_stack.append(vi)
vi = self.left[vi]
else:
l_stack.append(vi)
vi = self.right[vi]

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

return li, ri

def insert(self, x):

np = next(self.rand)

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

vi = self.root
pi = 0
d = 0

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

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

def delete(self, x):
vi = self.root
pi = 0
d = 0

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

if pi == 0:
self.root = vi
else:
self.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).
"""
vi = self.root
ti = 0
i = self.count[vi]
j = 0
while vi != 0:
if x < self.key[vi]:
ti = vi
i = j + self.count[self.left[vi]]
vi = self.left[vi]
else:
j += self.count[self.left[vi]] + 1
vi = self.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).
"""
vi = self.root
ti = 0
i = self.count[vi]
j = 0
while vi != 0:
if x <= self.key[vi]:
ti = vi
i = j + self.count[self.left[vi]]
vi = self.left[vi]
else:
j += self.count[self.left[vi]] + 1
vi = self.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.
"""
if i < 0 or self.get_size() <= i:
return 0
vi = self.root
j = i
while vi != 0:
l_cnt = self.count[self.left[vi]]
if l_cnt == j:
return vi
if j < l_cnt:
vi = self.left[vi]
else:
j -= l_cnt + 1
vi = self.right[vi]

assert False, 'Unreachable'

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

def get_prev(self, i, vi):
if vi == 0:
return 0
if self.left[vi] == 0:
return self.get_by_index(i - 1)
vi = self.left[vi]
while self.right[vi] != 0:
vi = self.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:39:20+0900 C - Maximize Minimum ikatakos PyPy3 (2.4.0) 0 9361 Byte TLE 4211 ms 164988 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
 AC × 2
 AC × 26 TLE × 1
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 166 ms 38256 KB
01-02.txt AC 610 ms 68824 KB
01-03.txt AC 544 ms 61912 KB
01-04.txt AC 550 ms 62424 KB
01-05.txt AC 530 ms 63964 KB
01-06.txt AC 501 ms 60888 KB
01-07.txt AC 512 ms 62300 KB
01-08.txt AC 548 ms 64988 KB
01-09.txt AC 521 ms 62552 KB
01-10.txt AC 518 ms 65496 KB
01-11.txt AC 599 ms 68316 KB
01-12.txt AC 577 ms 69724 KB
01-13.txt AC 621 ms 68700 KB
01-14.txt TLE 4211 ms 131448 KB
01-15.txt AC 2283 ms 144212 KB
01-16.txt AC 2006 ms 138708 KB
01-17.txt AC 2246 ms 146808 KB
01-18.txt AC 2471 ms 137936 KB
01-19.txt AC 2829 ms 155220 KB
01-20.txt AC 2864 ms 155180 KB
01-21.txt AC 2728 ms 161280 KB
01-22.txt AC 2952 ms 164988 KB
01-23.txt AC 3094 ms 141656 KB
01-24.txt AC 2984 ms 159996 KB
01-25.txt AC 3077 ms 143028 KB
sample-01.txt AC 168 ms 38256 KB
sample-02.txt AC 168 ms 38256 KB