結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
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()] * nself.__n = len(v)self.__log = (self.__n - 1).bit_length()self.__size = 1 << self.__logself.__d = [e()] * (2 * self.__size)self.__lz = [id()] * self.__sizeself.__op = opself.__e = eself.__mapping = mappingself.__composition = compositionself.__id = idfor 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.__sizefor i in range(self.__log, 0, -1):self.__push(p >> i)self.__d[p] = xfor i in range(1, self.__log + 1):self.__update(p >> i)def get(self, p: int):assert (0 <= p) & (p < self.__n)p += self.__sizefor 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.__sizer += self.__sizefor 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 += 1if(r & 1):r -= 1smr = self.__op(self.__d[r], smr)l //= 2r //= 2return 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.__sizefor 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):returnl += self.__sizer += self.__sizefor 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, rwhile(l < r):if(l & 1):self.__all_apply(l, f)l += 1if(r & 1):r -= 1self.__all_apply(r, f)l //= 2r //= 2l, r = l2, r2for 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.__nl += self.__sizefor i in range(self.__log, 0, -1):self.__push(l >> i)sm = self.__e()while(True):while(l % 2 == 0):l //= 2if(not g(self.__op(sm, self.__d[l]))):while(l < self.__size):self.__push(l)l *= 2if(g(self.__op(sm, self.__d[l]))):sm = self.__op(sm, self.__d[l])l += 1return l - self.__sizesm = self.__op(sm, self.__d[l])l += 1if(l & -l) == l:breakreturn self.__ndef min_left(self, r: int, g):assert (0 <= r) & (r <= self.__n)assert g(self.__e())if(r == 0):return 0r += self.__sizefor i in range(self.__log, 0, -1):self.__push((r-1) >> i)sm = self.__e()while(True):r -= 1while(r > 1) & (r % 2):r //= 2if(not g(self.__op(self.__d[r], sm))):while(r < self.__size):self.__push(r)r = 2 * r + 1if(g(self.__op(self.__d[r], sm))):sm = self.__op(self.__d[r], sm)r -= 1return r + 1 - self.__sizesm = self.__op(self.__d[r], sm)if(r & -r) == r:breakreturn 0def 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 xreturn fdef composition(f,g):return max(f,g)v = [0]*nlst = 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] = ielse: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)