結果

問題 No.318 学学学学学
ユーザー ccppjsrb
提出日時 2020-09-05 19:03:16
言語 Go
(1.23.4)
結果
AC  
実行時間 365 ms / 2,000 ms
コード長 7,351 bytes
コンパイル時間 14,632 ms
コンパイル使用メモリ 223,060 KB
実行使用メモリ 28,544 KB
最終ジャッジ日時 2024-11-29 05:57:05
合計ジャッジ時間 20,680 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)
func configure(scanner *bufio.Scanner) {
    scanner.Split(bufio.ScanWords)
    scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
    scanned := scanner.Scan()
    if !scanned {
        panic("scan failed")
    }
    return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
    i, _ := strconv.Atoi(getNextString(scanner))
    return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
    i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
    return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
    i, _ := strconv.ParseFloat(getNextString(scanner), 64)
    return i
}
func main() {
    fp := os.Stdin
    wfp := os.Stdout
    extra := 0
    if os.Getenv("I") == "IronMan" {
        fp, _ = os.Open(os.Getenv("END_GAME"))
        extra = 100
    }
    scanner := bufio.NewScanner(fp)
    configure(scanner)
    writer := bufio.NewWriter(wfp)
    defer func() {
        r := recover()
        if r != nil {
            fmt.Fprintln(writer, r)
        }
        writer.Flush()
    }()
    solve(scanner, writer)
    for i := 0; i < extra; i++ {
        fmt.Fprintln(writer, "-----------------------------------")
        solve(scanner, writer)
    }
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
    n := getNextInt(scanner)
    aa := make([]int, n)
    t := newTreeWithIntComparator()
    for i := 0; i < n; i++ {
        aa[i] = getNextInt(scanner)
        p, found := t.Get(aa[i])
        if found {
            t.Put(aa[i], pair{min(p.(pair)[0], i), max(p.(pair)[1], i)})
            continue
        }
        t.Put(aa[i], pair{i, i})
    }
    bb := make([]int, n)
    ll := make([][]int, n)
    rr := make([][]int, n)
    for !t.Empty() {
        p := t.Right()
        l := p.Value.(pair)[0]
        r := p.Value.(pair)[1]
        k := p.Key.(int)
        ll[l] = append(ll[l], k)
        rr[r] = append(rr[r], k)
        t.Remove(p.Key)
    }
    for i := 0; i < n; i++ {
        if len(ll[i]) > 0 {
            for _, v := range ll[i] {
                t.Put(v, nil)
            }
        }
        bb[i] = t.Right().Key.(int)
        if len(rr[i]) > 0 {
            for _, v := range rr[i] {
                t.Remove(v)
            }
        }
    }
    fmt.Fprint(writer, bb[0])
    for i := 1; i < n; i++ {
        fmt.Fprintf(writer, " %d", bb[i])
    }
    fmt.Fprintln(writer, "")
}
type pair [2]int
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func max(a, b int) int {
    return -min(-a, -b)
}
type tree struct {
    Root       *node
    Comparator func(a, b interface{}) int
}
type node struct {
    Left, Right, Parent *node
    Key                 interface{}
    Value               interface{}
    size                int
}
func newTreeWithIntComparator() *tree {
    return newTree(func(a, b interface{}) int {
        aa := a.(int)
        bb := b.(int)
        if aa == bb {
            return 0
        }
        if aa < bb {
            return -1
        }
        return 1
    })
}
func newTree(comparator func(interface{}, interface{}) int) *tree {
    return &tree{Root: nil, Comparator: comparator}
}
func newNode(parent *node, key, value interface{}) *node {
    return &node{Parent: parent, Key: key, Value: value, size: 1}
}
func (n *node) IsRoot() bool {
    return n.Parent == nil
}
func (n *node) IsLeft() bool {
    return !n.IsRoot() && n.Parent.Left == n
}
func (n *node) IsRight() bool {
    return !n.IsRoot() && n.Parent.Right == n
}
func (n *node) Update() {
    n.size = 1 + n.Left.Size() + n.Right.Size()
}
func (n *node) Size() int {
    if n == nil {
        return 0
    }
    return n.size
}
func (n *node) Merge(m *node) *node {
    if n == nil {
        return m
    }
    if m == nil {
        return n
    }
    if n.Size() > m.Size() {
        n.AppendRight(n.Right.Merge(m))
        n.Update()
        return n
    }
    m.AppendLeft(n.Merge(m.Left))
    m.Update()
    return m
}
func (n *node) MaximumNode() *node {
    if n == nil {
        return n
    }
    if n.Right == nil {
        return n
    }
    return n.Right.MaximumNode()
}
func (n *node) MinimumNode() *node {
    if n == nil {
        return n
    }
    if n.Left == nil {
        return n
    }
    return n.Left.MinimumNode()
}
func (n *node) AppendLeft(m *node) {
    if n == nil {
        return
    }
    n.Left = m
    n.Update()
    if m == nil {
        return
    }
    m.Parent = n
}
func (n *node) AppendRight(m *node) {
    if n == nil {
        return
    }
    n.Right = m
    n.Update()
    if m == nil {
        return
    }
    m.Parent = n
}
func (t *tree) Put(key, value interface{}) {
    if t.Root == nil {
        t.Root = newNode(nil, key, value)
        return
    }
    now := t.Root
    for {
        compared := t.Comparator(key, now.Key)
        switch {
        case compared == 0:
            now.Value = value
            return
        case compared < 0:
            if now.Left == nil {
                now.Left = newNode(now, key, value)
                t.Update(now)
                return
            }
            now = now.Left
        case compared > 0:
            if now.Right == nil {
                now.Right = newNode(now, key, value)
                t.Update(now)
                return
            }
            now = now.Right
        }
    }
}
func (t *tree) Get(key interface{}) (interface{}, bool) {
    now := t.Lookup(key)
    if now == nil {
        return nil, false
    }
    return now.Value, true
}
func (t *tree) Lookup(key interface{}) *node {
    now := t.Root
    for now != nil {
        compared := t.Comparator(key, now.Key)
        switch {
        case compared == 0:
            return now
        case compared < 0:
            now = now.Left
        case compared > 0:
            now = now.Right
        }
    }
    return nil
}
func (t *tree) Remove(key interface{}) {
    now := t.Lookup(key)
    if now == nil {
        return
    }
    parent := now.Parent
    partialTree := now.Left.Merge(now.Right)
    switch {
    case now.IsRoot():
        t.Root = partialTree
        if t.Root != nil {
            t.Root.Parent = nil
        }
    case now.IsLeft():
        parent.AppendLeft(partialTree)
    case now.IsRight():
        parent.AppendRight(partialTree)
    }
    for parent != nil {
        parent.Update()
        parent = parent.Parent
    }
}
func (t *tree) Update(now *node) {
    for now != nil {
        now.Update()
        parent := now.Parent
        switch {
        case now.Left.Size() > now.Right.Size():
            t.RotateRight(now.Left)
        case now.Left.Size() < now.Right.Size():
            t.RotateLeft(now.Right)
        }
        now = parent
    }
}
func (t *tree) RotateLeft(now *node) {
    parent := now.Parent
    grand := parent.Parent
    parent.AppendRight(now.Left)
    now.AppendLeft(parent)
    switch {
    case grand == nil:
        t.Root = now
        now.Parent = nil
    case grand.Left == parent:
        grand.AppendLeft(now)
    case grand.Right == parent:
        grand.AppendRight(now)
    }
}
func (t *tree) RotateRight(now *node) {
    parent := now.Parent
    grand := parent.Parent
    parent.AppendLeft(now.Right)
    now.AppendRight(parent)
    switch {
    case grand == nil:
        t.Root = now
        t.Root.Update()
        now.Parent = nil
    case grand.Left == parent:
        grand.AppendLeft(now)
    case grand.Right == parent:
        grand.AppendRight(now)
    }
}
func (t *tree) Right() *node {
    return t.Root.MaximumNode()
}
func (t *tree) Left() *node {
    return t.Root.MinimumNode()
}
func (t *tree) Floor(key interface{}) (*node, bool) {
    now := t.Root
    var n *node
    for now != nil {
        compared := t.Comparator(key, now.Key)
        switch {
        case compared == 0:
            return now, true
        case compared < 0:
            now = now.Left
        case compared > 0:
            n = now
            now = now.Right
        }
    }
    return n, n != nil
}
func (t *tree) Ceiling(key interface{}) (*node, bool) {
    now := t.Root
    var n *node
    for now != nil {
        compared := t.Comparator(key, now.Key)
        switch {
        case compared == 0:
            return now, true
        case compared < 0:
            n = now
            now = now.Left
        case compared > 0:
            now = now.Right
        }
    }
    return n, n != nil
}
func (t *tree) Empty() bool {
    return t.Root == nil
}
func (t *tree) At(i int) (*node, bool) {
    var n *node
    now := t.Root
    for now != nil && i > 0 {
        if i <= now.Left.Size() {
            now = now.Left
            continue
        }
        i -= now.Left.Size() + 1
        if i <= 0 {
            n = now
        }
        now = now.Right
    }
    return n, n != nil
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0