結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2021-12-28 16:07:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 523 ms / 2,000 ms |
コード長 | 3,210 bytes |
コンパイル時間 | 1,094 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 130,024 KB |
最終ジャッジ日時 | 2024-10-02 08:43:23 |
合計ジャッジ時間 | 10,086 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
class LazySegTree:# RMQ and RUQdef __init__(self, init_val, seg_ide, lazy_ide, segfunc):self.n = len(init_val)self.num = 2**(self.n-1).bit_length()self.seg_ide = seg_ideself.lazy_ide = lazy_ideself.segfunc = segfunc# seg, lazy: 1-indexedself.seg = [seg_ide]*2*self.numfor i in range(self.n):self.seg[i+self.num] = init_val[i]for i in range(self.num-1, 0, -1):self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])self.lazy = [lazy_ide]*2*self.numdef gindex(self, l, r):# l, r: 1-indexedL = l + self.numR = r + self.numlm = (L // (L & -L)) >> 1rm = (R // (R & -R)) >> 1while L < R:if R <= rm:yield Rif L <= lm:yield LL = L >> 1R = R >> 1while L:yield LL = L >> 1def propagate(self, *ids):# ids: 1-indexedfor i in reversed(ids):v = self.lazy[i]if v is None:continueself.lazy[2*i] = self.lazy[2*i+1] = self.seg[2*i] = self.seg[2*i+1] = vself.lazy[i] = Nonedef update(self, l, r, x):# l, r: 0-indexed# change x to [l, r)*ids, = self.gindex(l, r)self.propagate(*ids)L = l + self.numR = r + self.numwhile L < R:if R & 1:R -= 1self.lazy[R] = self.seg[R] = xif L & 1:self.lazy[L] = self.seg[L] = xL += 1L = L >> 1R = R >> 1for i in ids:# i: 1-indexedself.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])def query(self, l, r):# l, r: 0-indexed# query for [l, r)if r <= l:return self.seg_ideself.propagate(*self.gindex(l, r))L = l + self.numR = r + self.numres = self.seg_idewhile L < R:if R & 1:R -= 1res = self.segfunc(res, self.seg[R])if L & 1:res = self.segfunc(self.seg[L], res)L += 1L = L >> 1R = R >> 1return resdef __str__(self): # for debugarr = [self.query(i,i+1) for i in range(self.n)]return str(arr)import sysimport io, osinput = io.BytesIO(os.read(0,os.fstat(0).st_size)).readlinedef main():n = int(input())A = list(map(int, input().split()))X = set(A)X = list(X)X.sort()toid = {}for i, x in enumerate(X):toid[x] = iA = [toid[a] for a in A]N = len(X)I = [[] for i in range(N)]for i, a in enumerate(A):I[a].append(i)seg = LazySegTree([-1]*n, -1, None, max)for t in range(N):if not I[t]:continuel = I[t][0]r = I[t][-1]seg.update(l, r+1, t)ans = [0]*nfor i in range(n):j = seg.query(i, i+1)ans[i] = X[j]print(*ans)if __name__ == '__main__':main()