結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー aru aru
提出日時 2020-10-24 21:48:29
言語 Go
(1.23.4)
結果
AC  
実行時間 159 ms / 2,000 ms
コード長 6,704 bytes
コンパイル時間 11,412 ms
コンパイル使用メモリ 240,872 KB
実行使用メモリ 12,800 KB
最終ジャッジ日時 2024-07-21 15:46:25
合計ジャッジ時間 15,879 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)
var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)
func out(x ...interface{}) {
    fmt.Fprintln(wr, x...)
}
func getI() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}
func getF() float64 {
    sc.Scan()
    i, e := strconv.ParseFloat(sc.Text(), 64)
    if e != nil {
        panic(e)
    }
    return i
}
func getInts(N int) []int {
    ret := make([]int, N)
    for i := 0; i < N; i++ {
        ret[i] = getI()
    }
    return ret
}
func getS() string {
    sc.Scan()
    return sc.Text()
}
// min, max, asub, absなど基本関数
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func asub(a, b int) int {
    if a > b {
        return a - b
    }
    return b - a
}
func abs(a int) int {
    if a >= 0 {
        return a
    }
    return -a
}
func lowerBound(a []int, x int) int {
    idx := sort.Search(len(a), func(i int) bool {
        return a[i] >= x
    })
    return idx
}
func upperBound(a []int, x int) int {
    idx := sort.Search(len(a), func(i int) bool {
        return a[i] > x
    })
    return idx
}
func f(a, b []int, n int) int {
    ans := 0
    for i := 0; i < n; i++ {
        for a[i] != b[i] {
            for k := i + 1; k < n; k++ {
                if b[k] == a[i] {
                    b[k], b[k-1] = b[k-1], b[k]
                    ans++
                    break
                }
            }
        }
    }
    return ans
}
func main() {
    defer wr.Flush()
    sc.Split(bufio.ScanWords)
    sc.Buffer([]byte{}, 1000000)
    // this template is new version.
    // use getI(), getS(), getInts(), getF()
    n := getI()
    a := getInts(n)
    b := getInts(n)
    // res := f(a, b, n)
    // out(res)
    var e = func() S {
        return S{0}
    }
    var merger = func(a, b S) S {
        if a.a > b.a {
            return a
        }
        return b
    }
    var mapper = func(a F, b S) S {
        return S{a.a + b.a}
    }
    var comp = func(f, g F) F {
        return F{f.a + g.a}
    }
    var id = func() F {
        return F{0}
    }
    x := make([]S, n)
    m := make(map[int]int)
    for i := 0; i < n; i++ {
        x[i] = S{i}
        m[b[i]] = i
    }
    lseg := newLazySegtree(x, e, merger, mapper, comp, id)
    ans := 0
    for i := 0; i < n; i++ {
        pos := m[a[i]]
        cur := lseg.Get(pos).a
        lseg.RangeApply(0, pos, F{1})
        ans += cur - i
        // out(a[i], "cur", i, cur, "dist:", cur-i, lseg.Get(pos))
        // for a[i] != b[i] {
        //  for k := i + 1; k < n; k++ {
        //      if b[k] == a[i] {
        //          b[k], b[k-1] = b[k-1], b[k]
        //          ans++
        //          break
        //      }
        //  }
        // }
    }
    out(ans)
}
type S struct {
    a int
}
type F struct {
    a int
}
type E func() S
type Merger func(a, b S) S
type Mapper func(f F, x S) S
type Comp func(f, g F) F
type Id func() F
type Compare func(v S) bool
type LazySegtree struct {
    n      int
    size   int
    log    int
    d      []S
    lz     []F
    e      E
    merger Merger
    mapper Mapper
    comp   Comp
    id     Id
}
func newLazySegtree(v []S, e E, merger Merger, mapper Mapper, comp Comp, id Id) *LazySegtree {
    lseg := new(LazySegtree)
    lseg.n = len(v)
    lseg.log = lseg.ceilPow2(lseg.n)
    lseg.size = 1 << uint(lseg.log)
    lseg.d = make([]S, 2*lseg.size)
    lseg.e = e
    lseg.lz = make([]F, lseg.size)
    lseg.merger = merger
    lseg.mapper = mapper
    lseg.comp = comp
    lseg.id = id
    for i, _ := range lseg.d {
        lseg.d[i] = lseg.e()
    }
    for i, _ := range lseg.lz {
        lseg.lz[i] = lseg.id()
    }
    for i := 0; i < lseg.n; i++ {
        lseg.d[lseg.size+i] = v[i]
    }
    for i := lseg.size - 1; i >= 1; i-- {
        lseg.Update(i)
    }
    return lseg
}
func (lseg *LazySegtree) Update(k int) {
    lseg.d[k] = lseg.merger(lseg.d[2*k], lseg.d[2*k+1])
}
func (lseg *LazySegtree) AllApply(k int, f F) {
    lseg.d[k] = lseg.mapper(f, lseg.d[k])
    if k < lseg.size {
        lseg.lz[k] = lseg.comp(f, lseg.lz[k])
    }
}
func (lseg *LazySegtree) Push(k int) {
    lseg.AllApply(2*k, lseg.lz[k])
    lseg.AllApply(2*k+1, lseg.lz[k])
    lseg.lz[k] = lseg.id()
}
func (lseg *LazySegtree) Set(p int, x S) {
    p += lseg.size
    for i := lseg.log; i <= 1; i-- {
        lseg.Push(p >> uint(i))
    }
    lseg.d[p] = x
    for i := 1; i <= lseg.log; i++ {
        lseg.Update(p >> uint(i))
    }
}
func (lseg *LazySegtree) Get(p int) S {
    p += lseg.size
    for i := lseg.log; i >= 1; i-- {
        lseg.Push(p >> uint(i))
    }
    return lseg.d[p]
}
func (lseg *LazySegtree) Prod(l, r int) S {
    if l == r {
        return lseg.e()
    }
    l += lseg.size
    r += lseg.size
    for i := lseg.log; i >= 1; i-- {
        if (l>>uint(i))<<uint(i) != l {
            lseg.Push(l >> uint(i))
        }
        if (r>>uint(i))<<uint(i) != r {
            lseg.Push(r >> uint(i))
        }
    }
    sml, smr := lseg.e(), lseg.e()
    for l < r {
        if (l & 1) == 1 {
            sml = lseg.merger(sml, lseg.d[l])
            l++
        }
        if (r & 1) == 1 {
            r--
            smr = lseg.merger(lseg.d[r], smr)
        }
        l >>= 1
        r >>= 1
    }
    return lseg.merger(sml, smr)
}
func (lseg *LazySegtree) AllProd() S {
    return lseg.d[1]
}
func (lseg *LazySegtree) Apply(p int, f F) {
    p += lseg.size
    for i := lseg.log; i >= 1; i-- {
        lseg.Push(p >> uint(i))
    }
    lseg.d[p] = lseg.mapper(f, lseg.d[p])
    for i := 1; i <= lseg.log; i++ {
        lseg.Update(p >> uint(i))
    }
}
func (lseg *LazySegtree) RangeApply(l int, r int, f F) {
    if l == r {
        return
    }
    l += lseg.size
    r += lseg.size
    for i := lseg.log; i >= 1; i-- {
        if (l>>uint(i))<<uint(i) != l {
            lseg.Push(l >> uint(i))
        }
        if (r>>uint(i))<<uint(i) != r {
            lseg.Push((r - 1) >> uint(i))
        }
    }
    l2, r2 := l, r
    for l < r {
        if l&1 == 1 {
            lseg.AllApply(l, f)
            l++
        }
        if r&1 == 1 {
            r--
            lseg.AllApply(r, f)
        }
        l >>= 1
        r >>= 1
    }
    l, r = l2, r2
    for i := 1; i <= lseg.log; i++ {
        if (l>>uint(i))<<uint(i) != l {
            lseg.Update(l >> uint(i))
        }
        if (r>>uint(i))<<uint(i) != r {
            lseg.Update((r - 1) >> uint(i))
        }
    }
}
func (lseg *LazySegtree) MaxRight(l int, cmp Compare) int {
    if l == lseg.n {
        return lseg.n
    }
    l += lseg.size
    for i := lseg.log; i >= 1; i-- {
        lseg.Push(l >> uint(i))
    }
    sm := lseg.e()
    for {
        for l%2 == 0 {
            l >>= 1
        }
        if !cmp(lseg.merger(sm, lseg.d[l])) {
            for l < lseg.size {
                lseg.Push(l)
                l = 2 * l
                if cmp(lseg.merger(sm, lseg.d[l])) {
                    sm = lseg.merger(sm, lseg.d[l])
                    l++
                }
            }
            return l - lseg.size
        }
        sm = lseg.merger(sm, lseg.d[l])
        l++
        if l&-l == l {
            break
        }
    }
    return lseg.n
}
func (lseg *LazySegtree) MinLeft(r int, cmp Compare) int {
    if r == 0 {
        return 0
    }
    r += lseg.size
    for i := lseg.log; i >= 1; i-- {
        lseg.Push(r - 1>>uint(i))
    }
    sm := lseg.e()
    for {
        r--
        for r > 1 && r%2 != 0 {
            r >>= 1
        }
        if !cmp(lseg.merger(lseg.d[r], sm)) {
            for r < lseg.size {
                lseg.Push(r)
                r = 2*r + 1
                if cmp(lseg.merger(lseg.d[r], sm)) {
                    sm = lseg.merger(lseg.d[r], sm)
                    r--
                }
            }
            return r + 1 - lseg.size
        }
        sm = lseg.merger(lseg.d[r], sm)
        if r&-r == r {
            break
        }
    }
    return 0
}
func (lseg *LazySegtree) ceilPow2(n int) int {
    x := 0
    for (1 << uint(x)) < n {
        x++
    }
    return x
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0