結果

問題 No.318 学学学学学
ユーザー qumazakiqumazaki
提出日時 2020-09-26 03:08:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 576 ms / 2,000 ms
コード長 6,042 bytes
コンパイル時間 1,309 ms
コンパイル使用メモリ 87,032 KB
実行使用メモリ 106,956 KB
最終ジャッジ日時 2023-09-10 20:59:34
合計ジャッジ時間 12,263 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 195 ms
81,168 KB
testcase_01 AC 210 ms
82,532 KB
testcase_02 AC 283 ms
84,720 KB
testcase_03 AC 212 ms
81,804 KB
testcase_04 AC 233 ms
83,272 KB
testcase_05 AC 512 ms
106,852 KB
testcase_06 AC 503 ms
95,996 KB
testcase_07 AC 453 ms
95,940 KB
testcase_08 AC 418 ms
96,028 KB
testcase_09 AC 377 ms
95,964 KB
testcase_10 AC 273 ms
95,732 KB
testcase_11 AC 530 ms
106,956 KB
testcase_12 AC 576 ms
96,500 KB
testcase_13 AC 490 ms
95,904 KB
testcase_14 AC 452 ms
96,140 KB
testcase_15 AC 408 ms
95,900 KB
testcase_16 AC 260 ms
95,692 KB
testcase_17 AC 368 ms
99,180 KB
testcase_18 AC 397 ms
96,912 KB
testcase_19 AC 332 ms
98,940 KB
testcase_20 AC 338 ms
94,276 KB
testcase_21 AC 73 ms
71,300 KB
testcase_22 AC 75 ms
71,392 KB
testcase_23 AC 74 ms
71,148 KB
testcase_24 AC 75 ms
71,284 KB
testcase_25 AC 73 ms
71,388 KB
testcase_26 AC 76 ms
71,380 KB
testcase_27 AC 75 ms
71,384 KB
testcase_28 AC 76 ms
71,144 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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