結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー None
提出日時 2021-02-24 03:46:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 8,522 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 117,940 KB
最終ジャッジ日時 2024-09-22 22:48:57
合計ジャッジ時間 22,551 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LazySegmentTree():

    def __init__(self, n, f, g, merge, ef, eh):
        self.n = n
        self.f = f
        self.g = lambda xh, x: g(xh, x) if xh != eh else x
        self.merge = merge
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0

    def build(self, array):
        """
        bulid seg tree from array
        """
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """
        update (=replace) st[i] by x
        NOT update_range(i,i+1)
        """
        i += self.size
        self.propagate_lazy(i)
        self.tree[i] = x
        self.lazy[i] = self.eh
        self.propagate_tree(i)

    def get(self, i):
        i += self.size
        self.propagate_lazy(i)
        return self.g(self.lazy[i], self.tree[i])

    def update_range(self, l, r, x):
        """
        act op(x, a) on elements a in [l, r) ( 0-indexed ) ( O(logN) )
        """
        if l >= r:
            return
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1
                self.lazy[r] = self.merge(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.merge(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        get value from [l, r) (0-indexed)
        """
        l += self.size
        r += self.size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = self.ef
        res_r = self.ef
        while l < r:
            if l & 1:
                res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
            l >>= 1
            r >>= 1
        return self.f(res_l, res_r)

    def max_right(self,l,func):
        """
        return r such that
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l >= self.n: return self.n
        l += self.size
        s = self.ef
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not func(self.f(s,self.g(self.lazy[l],self.tree[l]))):
                while l < self.size:
                    l *= 2
                    if func(self.f(s,self.g(self.lazy[l],self.tree[l]))):
                        s = self.f(s, self.g(self.lazy[l], self.tree[l]))
                        l += 1
                return l - self.size
            s = self.f(s, self.g(self.lazy[l], self.tree[l]))
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self,r,func):
        """
        return l such that
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r <= 0: return 0
        r += self.size
        s = self.ef
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not func(self.f(self.g(self.lazy[r],self.tree[r]),s)):
                while r < self.size:
                    r = r * 2 + 1
                    if func(self.f(self.g(self.lazy[r],self.tree[r]),s)):
                        s = self.f(self.g(self.lazy[r], self.tree[r]), s)
                        r -= 1
                return r + 1 - self.size
            s = self.f(self.g(self.lazy[r], self.tree[r]), s)
            if r & -r == r: break
        return 0

    def propagate_lazy(self, i):
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if self.lazy[x] == self.eh:
                continue
            laz = self.lazy[x]
            self.lazy[(x<<1)|1] = self.merge(laz, self.lazy[(x << 1) | 1])
            self.lazy[x<<1] = self.merge(laz, self.lazy[x << 1])
            self.tree[x] = self.g(laz, self.tree[x])
            self.lazy[x] = self.eh

    def propagate_tree(self, i):
        while i>1:
            i>>=1
            self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1]))

    def __getitem__(self, i):
        if i<0: i=self.n+i
        return self.get(i)

    def __setitem__(self, i, value):
        if i<0: i=self.n+i
        self.update(i,value)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.eh:
                continue
            self.lazy[(x<<1)|1] = self.merge(self.lazy[x], self.lazy[(x << 1) | 1])
            self.lazy[x<<1] = self.merge(self.lazy[x], self.lazy[x << 1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            self.lazy[x] = self.eh
        for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]):
            yield self.g(xh,x)

    def __str__(self):
        return str(list(self))

    def debug(self):
        def full_tree_pos(G):
            n = G.number_of_nodes()
            if n == 0: return {}
            pos = {0: (0.5, 0.9)}
            if n == 1: return pos
            i = 1
            while not n >= 2 ** i or not n < 2 ** (i + 1): i+=1
            height = i
            p_key, p_y, p_x = 0, 0.9, 0.5
            l_child = True
            for i in range(height):
                for j in range(2 ** (i + 1)):
                    if 2 ** (i + 1) + j - 1 < n:
                        if l_child == True:
                            pos[2 ** (i + 1) + j - 1] = (p_x - 0.2 / (i * i + 1), p_y - 0.1)
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            l_child = False
                        else:
                            pos[2 ** (i + 1) + j - 1] = (p_x + 0.2 / (i * i + 1), p_y - 0.1)
                            l_child = True
                            G.add_edge(2 ** (i + 1) + j - 1, p_key)
                            p_key += 1
                            (p_x, p_y) = pos[p_key]
            return pos

        import networkx as nx
        import matplotlib.pyplot as plt
        A = self.tree[1:]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("tree-{0}.png".format(self.plt_cnt))
        plt.clf()

        A = self.lazy[1:-1]
        G = nx.Graph()
        labels = {}
        for i, a in enumerate(A):
            G.add_node(i)
            labels[i] = a
        pos = full_tree_pos(G)
        nx.draw(G, pos=pos, with_labels=True, labels=labels, node_size=1000)
        plt.savefig("lazy-{0}.png".format(self.plt_cnt))
        plt.clf()
        self.plt_cnt += 1

def max2(x,y):
    return x if x > y else y

def min2(x,y):
    return x if x < y else y


#############################################################
import sys
from bisect import *
from collections import Counter
input = sys.stdin.readline


def example():
    global input
    example = iter(
        """
2 1 1
0 2
        """
            .strip().split("\n"))
    input = lambda: next(example)

# example()


N,A,B=map(int, input().split())
X=list(map(int, input().split()))


####### 更新:代入 取得:min ########################################################
# get chain rule
def f(x,y):
    return x if x < y else y
ef = 10**6

# merge of update
def merge(a,b):
    return a if a != eh else b
eh = -1

# update chain rule
def g(a,x):
    return a

st = LazySegmentTree(N, f, g, merge, ef, eh)
################################################################################



st.build([i for i in range(N)])

for i in range(N):
    x=X[i]
    l=bisect_left(X,x+A)
    r=bisect_right(X,x+B)
    k=min2(st.get_range(l,min2(r,N)),st.get(i))
    st.update_range(l,min2(r,N),k)
    st.update_range(i,i+1,k)

C=Counter(st)

for i in range(N):
    k=st.get(i)
    print(C[k])
0