結果

問題 No.318 学学学学学
ユーザー sgsw
提出日時 2021-08-17 15:49:37
言語 Go
(1.23.4)
結果
AC  
実行時間 407 ms / 2,000 ms
コード長 6,605 bytes
コンパイル時間 15,227 ms
コンパイル使用メモリ 222,796 KB
実行使用メモリ 24,360 KB
最終ジャッジ日時 2024-10-10 13:37:38
合計ジャッジ時間 21,722 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
    "bufio"
    "fmt"
    "os"
    "reflect"
    "sort"
    "strconv"
)
var wg = bufio.NewScanner(os.Stdin)
const (
    inf            = (1 << 31) - 1
    initialBufSize = int(1e6)
    maxBufSize     = int(1e6)
)
var buf []byte = make([]byte, initialBufSize)
type Monoid int
func S_Op(x, y Monoid) Monoid {
    return x
}
func S_Ide() Monoid {
    return Monoid(inf)
}
////////////////////////////////////////////////////////
//Definition of Monoid F.
type op_Monoid int
func F_Op(x, y op_Monoid) op_Monoid {
    if y == -inf {
        return x
    }
    return y
}
func F_Ide() op_Monoid {
    return op_Monoid(-inf)
}
////////////////////////////////////////////////////////
//binary opearation S x F -> S
func binary_op(x Monoid, f op_Monoid) Monoid {
    if f == F_Ide() {
        return x
    }
    return Monoid(f)
}
type query struct {
    l, r, val int
}
func get_query(a []int) []query {
    d := make(map[int][]int)
    for i, v := range a {
        d[v] = append(d[v], i)
    }
    res := make([]query, 0)
    for k, v := range d {
        l := len(v)
        res = append(res, query{v[0], v[l-1], k})
    }
    sort.Slice(res, func(i, j int) bool {
        return res[i].val < res[j].val
    })
    return res
}
func main() {
    n := nextInt()
    a := make([]Monoid, n)
    seq := make([]int, n)
    for i := 0; i < n; i++ {
        seq[i] = nextInt()
        a[i] = Monoid(inf)
    }
    Q := get_query(seq)
    seg, _ := Gen(Monoid(0), op_Monoid(0), binary_op, S_Op, S_Ide, F_Op, F_Ide, n)
    SliceGen(seg, a)
    for _, q := range Q {
        l, r, val := q.l, q.r, q.val
        seg.Apply(l, r+1, op_Monoid(val))
    }
    ans := seg.GetThemAll()
    for i := 0; i < n; i++ {
        if i != n-1 {
            fmt.Printf("%d ", int(ans[i]))
        } else {
            fmt.Printf("%d\n", int(ans[i]))
        }
    }
}
func init() {
    wg.Split(bufio.ScanWords)
    wg.Buffer(buf, maxBufSize)
}
func nextInt() int {
    wg.Scan()
    i, e := strconv.Atoi(wg.Text())
    if e != nil {
        panic(e)
    }
    return i
}
/*
    Monoid-Structure should be decleared some-where else.
    -> op(Monoid,Monoid)Monoid & ide()Monoid is required.
*/
/*
    This is a example of (Monoid,op_Monoid).
    Any Pair of Monoid Would work.
*/
//Definition of Monoid S.
////////////////////////////////////////////////////////
type LazySegTree struct {
    monoid_type          Monoid
    operator_monoid_type op_Monoid
    //要素の演算定義
    op func(Monoid, Monoid) Monoid /* S x S-> S */
    e  func() Monoid               /*identity op of S (value-monoid)*/
    //作用素の演算定義
    operator_op func(op_Monoid, op_Monoid) op_Monoid /*f x f -> f*/
    operator_e  func() op_Monoid                     /*identity op of F(opearator-monoid)*/
    //作用素と要素の演算定義(右作用)
    binary_op func(Monoid, op_Monoid) Monoid /* S x F -> S */
    d    []Monoid
    _d   []Monoid
    _lz  []op_Monoid
    n    int /* size*/
    log  int
    size int
}
func Gen(monoid Monoid, op_monoid op_Monoid, binary_op_monoid func(Monoid, op_Monoid) Monoid, S_op func(Monoid, Monoid) Monoid, S_e func() Monoid, 
    F_op func(op_Monoid, op_Monoid) op_Monoid, F_e func() op_Monoid, n int) (LazySegTree, bool) {
    seg := LazySegTree{monoid_type: monoid, operator_monoid_type: op_monoid, op: S_op, e: S_e, operator_op: F_op, operator_e: F_e, binary_op: 
        binary_op_monoid, d: []Monoid{}, _d: []Monoid{}, n: 0, log: 0, size: 0}
    collect := true
    switch n > 0 {
    case true:
        seg.d = make([]Monoid, n)
        for i := range seg.d {
            seg.d[i] = seg.e()
        }
    default:
        collect = false
        return seg, collect
    }
    seg.n = len(seg.d)
    for ord := uint(0); (1 << ord) < seg.n; {
        ord++
        seg.log = int(ord)
    }
    seg.size = 1 << uint(seg.log)
    seg._d = make([]Monoid, 2*seg.size)
    seg._lz = make([]op_Monoid, seg.size)
    for i := range seg._d {
        seg._d[i] = seg.e()
    }
    for i := range seg._lz {
        seg._lz[i] = seg.operator_e()
    }
    for i := 0; i < seg.n; i++ {
        seg._d[seg.size+i] = seg.d[i]
    }
    for i := seg.size - 1; i > 0; i-- {
        seg._update(i)
    }
    return seg, collect
}
func SliceGen(seg LazySegTree, array []Monoid) bool {
    ok := true
    if len(array) != seg.n {
        ok = false
        return ok
    }
    for _, v := range array {
        if reflect.TypeOf(seg.monoid_type) != reflect.TypeOf(v) {
            ok = false
            return ok
        }
    }
    for i := 0; i < seg.n; i++ {
        seg._d[seg.size+i] = array[i]
    }
    for i := seg.size - 1; i > 0; i-- {
        seg._update(i)
    }
    return ok
}
func (seg LazySegTree) _update(k int) {
    seg._d[k] = seg.op(seg._d[2*k], seg._d[2*k+1])
}
func (seg LazySegTree) _all_apply(k int, f op_Monoid) {
    seg._d[k] = seg.binary_op(seg._d[k], f)
    if k < seg.size {
        seg._lz[k] = seg.operator_op(seg._lz[k], f)
    }
}
func (seg LazySegTree) _push(k int) {
    seg._all_apply(k<<1, seg._lz[k])
    seg._all_apply((k<<1)+1, seg._lz[k])
    seg._lz[k] = seg.operator_e()
}
func (seg LazySegTree) Set(p int, x Monoid) {
    //a[p] -> x in O(logN).
    p += seg.size
    for i := uint(seg.log); i > 0; i-- {
        seg._push(p >> i)
    }
    seg._d[p] = x
    for i := uint(1); i <= uint(seg.log); i++ {
        seg._update(p >> i)
    }
}
func (seg LazySegTree) Get(p int) Monoid {
    // a[p] in O(logN).
    p += seg.size
    for i := uint(seg.log); i > 0; i-- {
        seg._push(p >> i)
    }
    return seg._d[p]
}
func (seg LazySegTree) GetThemAll() []Monoid {
    //get all element in O(N).
    for i := 0; i < seg.size; i++ {
        seg._push(i)
    }
    a := make([]Monoid, seg.n)
    for i := 0; i < seg.n; i++ {
        a[i] = seg._d[i+seg.size]
    }
    return a
}
func (seg LazySegTree) Prod(l, r int) Monoid {
    //a[l..r) in O(logN).
    sml := seg.e()
    smr := seg.e()
    l += seg.size
    r += seg.size
    for i := uint(seg.log); i > 0; i-- {
        if (l>>i)<<i != l {
            seg._push(l >> i)
        }
        if (r>>i)<<i != r {
            seg._push(r >> i)
        }
    }
    for l < r {
        if l&1 == 1 {
            sml = seg.op(sml, seg._d[l])
            l++
        }
        if r&1 == 1 {
            r--
            smr = seg.op(seg._d[r], smr)
        }
        l >>= 1
        r >>= 1
    }
    return seg.op(sml, smr)
}
func (seg LazySegTree) AllProd() Monoid {
    return seg._d[1]
}
func (seg LazySegTree) ApplyOne(l int, f func(Monoid) Monoid) {
    // a[l] -> f(a[l]) in O(logN).
    p := l + seg.size
    for i := uint(seg.log); i > 0; i-- {
        seg._push(p >> i)
    }
    seg._d[p] = f(seg._d[p])
    for i := uint(1); i <= uint(seg.log); i++ {
        seg._update(p >> i)
    }
}
func (seg LazySegTree) Apply(l, r int, f op_Monoid) {
    // a[l..r) -> f(a[l..r)) in O(logN).
    l += seg.size
    r += seg.size
    for i := uint(seg.log); i > 0; i-- {
        if (l>>i)<<i != l {
            seg._push(l >> i)
        }
        if (r>>i)<<i != r {
            seg._push((r - 1) >> i)
        }
    }
    l2, r2 := l, r
    for l < r {
        if l&1 == 1 {
            seg._all_apply(l, f)
            l++
        }
        if r&1 == 1 {
            r--
            seg._all_apply(r, f)
        }
        l >>= 1
        r >>= 1
    }
    l, r = l2, r2
    for i := uint(1); i <= uint(seg.log); i++ {
        if (l>>i)<<i != l {
            seg._update(l >> i)
        }
        if (r>>i)<<i != r {
            seg._update((r - 1) >> i)
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0