結果

問題 No.742 にゃんにゃんにゃん　猫の挨拶
ユーザー 草苺奶昔
提出日時 2023-04-13 01:53:14
言語 Go
(1.23.4)
結果
AC  
実行時間 95 ms / 2,500 ms
コード長 2,536 bytes
コンパイル時間 12,054 ms
コンパイル使用メモリ 233,076 KB
実行使用メモリ 19,712 KB
最終ジャッジ日時 2024-10-09 02:47:02
合計ジャッジ時間 13,161 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
    "bufio"
    "fmt"
    "os"
    "sort"
)
const INF int = 1e18
func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var n int
    fmt.Fscan(in, &n)
    xs := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &xs[i])
        xs[i]--
    }
    wm := NewSegmentTreeFractionalCascading(xs)
    res := n * (n - 1)
    for i := 0; i < n; i++ {
        res -= wm.Query(0, i, 0, xs[i])       // 左侧不相撞的
        res -= wm.Query(i+1, n, xs[i]+1, 2*n) // 右侧不相撞的
    }
    fmt.Fprintln(out, res/2)
}
type SegmentTreeFractionalCascading struct {
    seg, ll, rr [][]int
    sz          int
}
func NewSegmentTreeFractionalCascading(array []int) *SegmentTreeFractionalCascading {
    res := &SegmentTreeFractionalCascading{}
    n := len(array)
    sz := 1
    for sz < n {
        sz <<= 1
    }
    tmp := 2*sz - 1
    seg := make([][]int, tmp)
    ll := make([][]int, tmp)
    rr := make([][]int, tmp)
    for k := 0; k < n; k++ {
        seg[k+sz-1] = append(seg[k+sz-1], array[k])
    }
    for k := sz - 2; k >= 0; k-- {
        a, b := 2*k+1, 2*k+2
        seg[k] = make([]int, len(seg[a])+len(seg[b]))
        ll[k] = make([]int, len(seg[k])+1)
        rr[k] = make([]int, len(seg[k])+1)
        seg[k] = make([]int, 0, len(seg[a])+len(seg[b]))
        i, j := 0, 0
        for i < len(seg[a]) && j < len(seg[b]) {
            if seg[a][i] < seg[b][j] {
                seg[k] = append(seg[k], seg[a][i])
                i++
            } else {
                seg[k] = append(seg[k], seg[b][j])
                j++
            }
        }
        seg[k] = append(seg[k], seg[a][i:]...)
        seg[k] = append(seg[k], seg[b][j:]...)
        tail1, tail2 := 0, 0
        for i := 0; i < len(seg[k]); i++ {
            for tail1 < len(seg[a]) && seg[a][tail1] < seg[k][i] {
                tail1++
            }
            for tail2 < len(seg[b]) && seg[b][tail2] < seg[k][i] {
                tail2++
            }
            ll[k][i] = tail1
            rr[k][i] = tail2
        }
        ll[k][len(seg[k])] = len(seg[a])
        rr[k][len(seg[k])] = len(seg[b])
    }
    res.seg = seg
    res.ll = ll
    res.rr = rr
    res.sz = sz
    return res
}
// 查询区间 [start, end) 中，[floor, ceiling) 范围内的数的个数.
func (st *SegmentTreeFractionalCascading) Query(start, end, floor, ceiling int) int {
    floor = sort.SearchInts(st.seg[0], floor)
    ceiling = sort.SearchInts(st.seg[0], ceiling)
    return st._query(start, end, floor, ceiling, 0, 0, st.sz)
}
func (st *SegmentTreeFractionalCascading) _query(a, b, lower, upper, k, l, r int) int {
    if a >= r || b <= l {
        return 0
    }
    if a <= l && r <= b {
        return upper - lower
    }
    return st._query(a, b, st.ll[k][lower], st.ll[k][upper], 2*k+1, l, (l+r)>>1) + st._query(a, b, st.rr[k][lower], st.rr[k][upper], 2*k+2, (l+r)>>1, 
        r)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0