結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2019-08-11 13:33:37 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 197 ms / 2,000 ms |
コード長 | 4,138 bytes |
コンパイル時間 | 3,485 ms |
コンパイル使用メモリ | 73,812 KB |
実行使用メモリ | 12,572 KB |
最終ジャッジ日時 | 2024-07-02 15:50:40 |
合計ジャッジ時間 | 7,963 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 57) Warning: imported and not used: 'strutils' [UnusedImport]
ソースコード
#{{{ headerimport algorithm, sequtils, tables, macros, math, sets, strutilswhen defined(MYDEBUG):import headerproc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}proc getchar(): char {.header: "<stdio.h>", varargs.}proc nextInt(): int = scanf("%lld",addr result)proc nextFloat(): float = scanf("%lf",addr result)proc nextString(): string =var get = falseresult = ""while true:var c = getchar()if int(c) > int(' '):get = trueresult.add(c)else:if get: breakget = falsetemplate `max=`*(x,y:typed):void = x = max(x,y)template `min=`*(x,y:typed):void = x = min(x,y)template infty(T): untyped = ((T(1) shl T(sizeof(T)*8-2)) - 1)#}}}type LazySegmentTree[S,T] = objectf:proc(x,y:S):Sg:proc(x:S,d:T,n:int):Sh:proc(x,y:T):Tsz:intdata:seq[S]lazy:seq[T]M1:SOM0:Tproc newLazySegmentTree[S,T](n:int,f:proc(x,y:S):S, g:proc(x:S,d:T,n:int):S, h:proc(x,y:T):T, M1:S, OM0:T):LazySegmentTree[S,T] =var sz = 1while sz < n: sz *= 2return LazySegmentTree[S,T](f:f,g:g,h:h,sz:sz,data:newSeqWith(2*sz,M1),lazy:newSeqWith(2*sz,OM0))proc set[S,T](self:var LazySegmentTree[S,T], v:openarray[S]):void =for k in 0..<v.len: self.data[k+self.sz] = v[k]for k in countdown(self.sz-1,1):self.data[k] = self.f(self.data[2*k+0], self.data[2*k+1])proc set[S,T](self:var LazySegmentTree[S,T], a:int, x:S, k,l,r:int):S {.discardable.} =self.propagate(k, r - l)if a < l or r <= a: discardelif r - l == 1: self.data[k] = xelse:let m = ((l+r) shr 1)self.data[k] = self.f(self.set(a,x,k*2,l,m), self.set(a,x,k*2+1,m,r))return self.data[k]proc set[S,T](self:var LazySegmentTree[S,T], a:int, x:S):S {.discardable.} =return self.set(a, x, 1, 0, self.sz)proc propagate[S,T](self:var LazySegmentTree[S,T], k:int, len:int): void =if self.lazy[k] != self.OM0:if k < self.sz:self.lazy[2 * k + 0] = self.h(self.lazy[2 * k + 0], self.lazy[k])self.lazy[2 * k + 1] = self.h(self.lazy[2 * k + 1], self.lazy[k])self.data[k] = self.g(self.data[k], self.lazy[k], len);self.lazy[k] = self.OM0;proc update[S,T](self:var LazySegmentTree[S,T], a,b:int, x:T, k,l,r:int):S {.discardable.} =self.propagate(k, r - l)if r <= a or b <= l: return self.data[k]elif a <= l and r <= b:self.lazy[k] = self.h(self.lazy[k], x)self.propagate(k, r - l);return self.data[k]else:let m = ((l+r) shr 1)self.data[k] = self.f(self.update(a, b, x, 2 * k, l, m), self.update(a, b, x, 2 * k + 1, m, r))return self.data[k]proc update[S,T](self:var LazySegmentTree[S,T], a,b:int, x:T):void =discard self.update(a, b, x, 1, 0, self.sz)proc query[S,T](self:var LazySegmentTree[S,T], a,b,k,l,r:int):S =self.propagate(k, r - l)if r <= a or b <= l: return self.M1elif a <= l and r <= b: return self.data[k]else:let m = ((l+r) shr 1)return self.f(self.query(a, b, 2 * k + 0, l, m), self.query(a, b, 2 * k + 1, m, r))proc query[S,T](self:var LazySegmentTree[S,T], a,b:int):S =return self.query(a, b, 1, 0, self.sz)proc `[]`[S,T](self:var LazySegmentTree[S,T], k:int):S =return self.query(k, k + 1)proc write[S,T](self:var LazySegmentTree[S,T], h,k,l,r:int):void =for i in 0..h-1:stdout.write " "echo self.data[k]," ",self.lazy[k]if r - l > 1:let m = ((l+r) shr 1)self.write(h+1,k*2 ,l,m)self.write(h+1,k*2+1,m,r)proc write[S,T](self:var LazySegmentTree[S,T]):void =echo "tree: "self.write(0,1,0,self.sz)let INF = 10^9proc main():void =varn = nextInt()a = newSeqWith(n,nextInt())left = newSeqWith(n,INF)right = newSeqWith(n,-INF)proc f(a,b:int):int = return a + bproc g(a,d,n:int):int = return dproc h(a,b:int):int = return bvar st = newLazySegmentTree(n,f,g,h,0,-1)var v = av.sort()v = v.deduplicate(true)for i in 0..n-1:let id = binarySearch(v,a[i])left[id] = min(left[id],i)right[id] = max(left[id],i)for i in 0..n-1:if left[i] == INF: breakst.update(left[i],right[i]+1,v[i])for i in 0..n-1:stdout.write st[i]," "echo ""discardmain()