結果

問題 No.318 学学学学学
ユーザー chaemon
提出日時 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]

ソースコード

diff #
プレゼンテーションモードにする

#{{{ header
import algorithm, sequtils, tables, macros, math, sets, strutils
when defined(MYDEBUG):
import header
proc 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 = false
result = ""
while true:
var c = getchar()
if int(c) > int(' '):
get = true
result.add(c)
else:
if get: break
get = false
template `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] = object
f:proc(x,y:S):S
g:proc(x:S,d:T,n:int):S
h:proc(x,y:T):T
sz:int
data:seq[S]
lazy:seq[T]
M1:S
OM0:T
proc 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 = 1
while sz < n: sz *= 2
return 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: discard
elif r - l == 1: self.data[k] = x
else:
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.M1
elif 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^9
proc main():void =
var
n = nextInt()
a = newSeqWith(n,nextInt())
left = newSeqWith(n,INF)
right = newSeqWith(n,-INF)
proc f(a,b:int):int = return a + b
proc g(a,d,n:int):int = return d
proc h(a,b:int):int = return b
var st = newLazySegmentTree(n,f,g,h,0,-1)
var v = a
v.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: break
st.update(left[i],right[i]+1,v[i])
for i in 0..n-1:
stdout.write st[i]," "
echo ""
discard
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0