Submission #7993100


Source Code Expand

Copy
import sys

from collections import defaultdict
from heapq import heappush, heappop

# Performance Test
from random import randint


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

    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 = randint(1, 0xfffffff)

        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:
                self.deleted.add(vi)
                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:
        strawberry.add(a)
        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
Task C - Maximize Minimum
User ikatakos
Language PyPy3 (2.4.0)
Score 700
Code Size 9701 Byte
Status AC
Exec Time 3841 ms
Memory 184424 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 249 ms 40816 KB
01-02.txt AC 701 ms 78300 KB
01-03.txt AC 551 ms 62044 KB
01-04.txt AC 574 ms 64216 KB
01-05.txt AC 539 ms 63832 KB
01-06.txt AC 523 ms 62684 KB
01-07.txt AC 548 ms 67164 KB
01-08.txt AC 596 ms 72664 KB
01-09.txt AC 542 ms 64472 KB
01-10.txt AC 562 ms 70488 KB
01-11.txt AC 635 ms 71772 KB
01-12.txt AC 519 ms 62808 KB
01-13.txt AC 653 ms 72796 KB
01-14.txt AC 3778 ms 135124 KB
01-15.txt AC 2323 ms 144980 KB
01-16.txt AC 2026 ms 143060 KB
01-17.txt AC 2131 ms 146640 KB
01-18.txt AC 2376 ms 144464 KB
01-19.txt AC 2590 ms 150404 KB
01-20.txt AC 2629 ms 153600 KB
01-21.txt AC 3562 ms 184424 KB
01-22.txt AC 2713 ms 163816 KB
01-23.txt AC 3841 ms 166512 KB
01-24.txt AC 2786 ms 167272 KB
01-25.txt AC 2773 ms 142680 KB
sample-01.txt AC 175 ms 38640 KB
sample-02.txt AC 177 ms 38640 KB