#558797 (PyPy3) No.318 学学学学学

提出ソース

結果

問題	No.318 学学学学学
ユーザー	qumazaki
提出日時	2020-09-26 03:08:26
言語	PyPy3 (7.3.15)
結果	AC
実行時間	480 ms / 2,000 ms
コード長	6,042 bytes
コンパイル時間	572 ms
コンパイル使用メモリ	82,028 KB
実行使用メモリ	104,496 KB
最終ジャッジ日時	2024-06-28 12:05:22
合計ジャッジ時間	10,240 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	154 ms 79,324 KB
testcase_01	AC	163 ms 81,840 KB
testcase_02	AC	229 ms 82,996 KB
testcase_03	AC	156 ms 80,644 KB
testcase_04	AC	190 ms 82,488 KB
testcase_05	AC	480 ms 104,000 KB
testcase_06	AC	448 ms 98,008 KB
testcase_07	AC	408 ms 98,000 KB
testcase_08	AC	362 ms 97,608 KB
testcase_09	AC	331 ms 96,096 KB
testcase_10	AC	229 ms 94,788 KB
testcase_11	AC	475 ms 103,712 KB
testcase_12	AC	475 ms 97,620 KB
testcase_13	AC	437 ms 97,640 KB
testcase_14	AC	394 ms 97,668 KB
testcase_15	AC	348 ms 95,788 KB
testcase_16	AC	219 ms 94,652 KB
testcase_17	AC	331 ms 104,368 KB
testcase_18	AC	353 ms 101,364 KB
testcase_19	AC	291 ms 104,496 KB
testcase_20	AC	284 ms 93,132 KB
testcase_21	AC	40 ms 54,512 KB
testcase_22	AC	39 ms 54,124 KB
testcase_23	AC	39 ms 55,160 KB
testcase_24	AC	38 ms 53,656 KB
testcase_25	AC	39 ms 54,364 KB
testcase_26	AC	40 ms 54,040 KB
testcase_27	AC	41 ms 54,572 KB
testcase_28	AC	40 ms 54,972 KB

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

ソースコード

raw source code

class LazySegTree:
    def __init__(self, op, e, mapping, composition, id,
                 n: int = -1, v: list = []):
        assert (len(v) > 0) | (n > 0)
        if(len(v) == 0):
            v = [e()] * n
        self.__n = len(v)
        self.__log = (self.__n - 1).bit_length()
        self.__size = 1 << self.__log
        self.__d = [e()] * (2 * self.__size)
        self.__lz = [id()] * self.__size
        self.__op = op
        self.__e = e
        self.__mapping = mapping
        self.__composition = composition
        self.__id = id

        for i in range(self.__n):
            self.__d[self.__size + i] = v[i]
        for i in range(self.__size - 1, 0, -1):
            self.__update(i)

    def __update(self, k: int):
        self.__d[k] = self.__op(self.__d[2 * k], self.__d[2 * k + 1])

    def __all_apply(self, k: int, f):
        self.__d[k] = self.__mapping(f, self.__d[k])
        if(k < self.__size):
            self.__lz[k] = self.__composition(f, self.__lz[k])

    def __push(self, k: int):
        self.__all_apply(2*k, self.__lz[k])
        self.__all_apply(2*k+1, self.__lz[k])
        self.__lz[k] = self.__id()

    def set(self, p: int, x):
        assert (0 <= p) & (p < self.__n)
        p += self.__size
        for i in range(self.__log, 0, -1):
            self.__push(p >> i)
        self.__d[p] = x
        for i in range(1, self.__log + 1):
            self.__update(p >> i)

    def get(self, p: int):
        assert (0 <= p) & (p < self.__n)
        p += self.__size
        for i in range(self.__log, 0, -1):
            self.__push(p >> i)
        return self.__d[p]

    def prod(self, l: int, r: int):
        assert (0 <= l) & (l <= r) & (r <= self.__n)
        if(l == r):
            return self.__e()

        l += self.__size
        r += self.__size

        for i in range(self.__log, 0, -1):
            if((l >> i) << i) != l:
                self.__push(l >> i)
            if((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.__e()
        smr = self.__e()
        while(l < r):
            if(l & 1):
                sml = self.__op(sml, self.__d[l])
                l += 1
            if(r & 1):
                r -= 1
                smr = self.__op(self.__d[r], smr)
            l //= 2
            r //= 2

        return self.__op(sml, smr)

    def all_prod(self):
        return self.__d[1]

    def apply(self, p: int, f):
        assert (0 <= p) & (p < self.__n)
        p += self.__size
        for i in range(self.__log, 0, -1):
            self.__push(p >> i)
        self.__d[p] = self.__mapping(f, self.__d[p])
        for i in range(1, self.__log+1):
            self.__update(p >> i)

    def apply_lr(self, l: int, r: int, f):
        assert (0 <= l) & (l <= r) & (r <= self.__n)
        if(l == r):
            return

        l += self.__size
        r += self.__size

        for i in range(self.__log, 0, -1):
            if((l >> i) << i) != l:
                self.__push(l >> i)
            if((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2, r2 = l, r
        while(l < r):
            if(l & 1):
                self.__all_apply(l, f)
                l += 1
            if(r & 1):
                r -= 1
                self.__all_apply(r, f)
            l //= 2
            r //= 2
        l, r = l2, r2

        for i in range(1, self.__log+1):
            if((l >> i) << i) != l:
                self.__update(l >> i)
            if((r >> i) << i) != r:
                self.__update((r-1) >> i)

    def max_right(self, l: int, g):
        assert (0 <= l) & (l <= self.__n)
        assert g(self.__e())
        if(l == self.__n):
            return self.__n
        l += self.__size
        for i in range(self.__log, 0, -1):
            self.__push(l >> i)
        sm = self.__e()
        while(True):
            while(l % 2 == 0):
                l //= 2
            if(not g(self.__op(sm, self.__d[l]))):
                while(l < self.__size):
                    self.__push(l)
                    l *= 2
                    if(g(self.__op(sm, self.__d[l]))):
                        sm = self.__op(sm, self.__d[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__d[l])
            l += 1
            if(l & -l) == l:
                break
        return self.__n

    def min_left(self, r: int, g):
        assert (0 <= r) & (r <= self.__n)
        assert g(self.__e())
        if(r == 0):
            return 0
        r += self.__size
        for i in range(self.__log, 0, -1):
            self.__push((r-1) >> i)
        sm = self.__e()
        while(True):
            r -= 1
            while(r > 1) & (r % 2):
                r //= 2
            if(not g(self.__op(self.__d[r], sm))):
                while(r < self.__size):
                    self.__push(r)
                    r = 2 * r + 1
                    if(g(self.__op(self.__d[r], sm))):
                        sm = self.__op(self.__d[r], sm)
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(self.__d[r], sm)
            if(r & -r) == r:
                break
        return 0

    def all_push(self):
        for i in range(1,self.__size):
            self.__push(i)

    def get_all(self):
        self.all_push()
        return self.__d[self.__size:self.__size+self.__n]

n = int(input())
a = list(map(int,input().split()))

def mapping(f,x):
    if(f==0):
        return x
    return f

def composition(f,g):
    return max(f,g)

v = [0]*n
lst = LazySegTree(op=lambda x,y:0,
                  e=lambda: 0,
                  mapping=mapping,
                  composition=composition,
                  id=lambda: 0,
                  v=v
                  )

pos = {}
for i,ai in enumerate(a):
    if ai in pos:
        pos[ai][1] = i
    else:
        pos[ai] = [i,i]

nums = [i for i in pos.keys()]
nums.sort()

for i in nums:
    l,r = pos[i]
    lst.apply_lr(l,r+1, i)

ans = lst.get_all()
print(*ans)

yukicoder

結果

テストケース

ソースコード