結果

問題 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()
0