#621766 (PyPy3) No.1170 Never Want to Walk

提出ソース

結果

問題	No.1170 Never Want to Walk
ユーザー	None
提出日時	2021-02-24 03:30:41
言語	PyPy3 (7.3.15)
結果	WA
実行時間	-
コード長	8,251 bytes
コンパイル時間	197 ms
コンパイル使用メモリ	82,188 KB
実行使用メモリ	118,208 KB
最終ジャッジ日時	2024-09-22 22:33:18
合計ジャッジ時間	23,749 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	53 ms 56,676 KB
testcase_01	AC	46 ms 56,052 KB
testcase_02	AC	47 ms 56,980 KB
testcase_03	AC	45 ms 56,316 KB
testcase_04	AC	45 ms 57,504 KB
testcase_05	AC	45 ms 56,696 KB
testcase_06	AC	45 ms 56,408 KB
testcase_07	AC	45 ms 56,004 KB
testcase_08	AC	46 ms 56,808 KB
testcase_09	AC	45 ms 56,472 KB
testcase_10	AC	45 ms 56,388 KB
testcase_11	AC	45 ms 55,760 KB
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	164 ms 78,512 KB
testcase_23	AC	159 ms 77,668 KB
testcase_24	AC	154 ms 77,816 KB
testcase_25	AC	157 ms 77,256 KB
testcase_26	AC	163 ms 77,712 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	AC	1,338 ms 117,028 KB
testcase_33	AC	1,550 ms 117,236 KB
testcase_34	AC	1,312 ms 117,400 KB
testcase_35	AC	1,346 ms 117,312 KB
testcase_36	AC	1,243 ms 117,012 KB
testcase_37	AC	1,188 ms 117,108 KB
testcase_38	AC	1,361 ms 117,812 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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
#############################################################
import sys
from bisect import *
from collections import Counter
input = sys.stdin.readline


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 = 1<<22

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

# 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=min(st.get_range(l,min(r,N)),st.get(i))
    st.update_range(l,min(r,N),k)
    st[i]=k

C=Counter(st)

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

yukicoder

結果

テストケース

ソースコード