結果
問題 | No.1036 Make One With GCD 2 |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-10 19:26:19 |
言語 | Go (1.22.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,590 bytes |
コンパイル時間 | 10,415 ms |
コンパイル使用メモリ | 238,540 KB |
実行使用メモリ | 31,760 KB |
最終ジャッジ日時 | 2024-09-18 03:22:04 |
合計ジャッジ時間 | 18,534 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
ソースコード
package main import ( "bufio" "fmt" stdio "io" "os" "strconv" ) // from https://atcoder.jp/users/ccppjsrb var io *Iost type Iost struct { Scanner *bufio.Scanner Writer *bufio.Writer } func NewIost(fp stdio.Reader, wfp stdio.Writer) *Iost { const BufSize = 2000005 scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, BufSize), BufSize) return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)} } func (io *Iost) Text() string { if !io.Scanner.Scan() { panic("scan failed") } return io.Scanner.Text() } func (io *Iost) Atoi(s string) int { x, _ := strconv.Atoi(s); return x } func (io *Iost) Atoi64(s string) int64 { x, _ := strconv.ParseInt(s, 10, 64); return x } func (io *Iost) Atof64(s string) float64 { x, _ := strconv.ParseFloat(s, 64); return x } func (io *Iost) NextInt() int { return io.Atoi(io.Text()) } func (io *Iost) NextInt64() int64 { return io.Atoi64(io.Text()) } func (io *Iost) NextFloat64() float64 { return io.Atof64(io.Text()) } func (io *Iost) Print(x ...interface{}) { fmt.Fprint(io.Writer, x...) } func (io *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(io.Writer, s, x...) } func (io *Iost) Println(x ...interface{}) { fmt.Fprintln(io.Writer, x...) } func main() { in := os.Stdin out := os.Stdout io = NewIost(in, out) defer func() { io.Writer.Flush() }() n := io.NextInt() nums := make([]E, n) for i := 0; i < n; i++ { nums[i] = io.NextInt() } io.Println(solve(nums)) } func solve(nums []int) int { n := len(nums) res := 0 seg := NewSegmentTree(nums) for left := 0; left < n; left++ { right := seg.MaxRight(left, func(x int) bool { return x != 1 }) res += n - right } return res } type E = int func (*SegmentTree) e() E { return 0 } func (*SegmentTree) op(a, b E) E { for b != 0 { a, b = b, a%b } return a } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b } type SegmentTree struct { n, size int seg []E } func NewSegmentTree(leaves []E) *SegmentTree { res := &SegmentTree{} n := len(leaves) size := 1 for size < n { size <<= 1 } seg := make([]E, size<<1) for i := 0; i < n; i++ { seg[i+size] = leaves[i] } for i := size - 1; i > 0; i-- { seg[i] = res.op(seg[i<<1], seg[i<<1|1]) } res.n = n res.size = size res.seg = seg return res } func (st *SegmentTree) Get(index int) E { if index < 0 || index >= st.n { return st.e() } return st.seg[index+st.size] } func (st *SegmentTree) Set(index int, value E) { if index < 0 || index >= st.n { return } index += st.size st.seg[index] = value for index >>= 1; index > 0; index >>= 1 { st.seg[index] = st.op(st.seg[index<<1], st.seg[index<<1|1]) } } // [start, end) func (st *SegmentTree) Query(start, end int) E { if start < 0 { start = 0 } if end > st.n { end = st.n } if start >= end { return st.e() } leftRes, rightRes := st.e(), st.e() start += st.size end += st.size for start < end { if start&1 == 1 { leftRes = st.op(leftRes, st.seg[start]) start++ } if end&1 == 1 { end-- rightRes = st.op(st.seg[end], rightRes) } start >>= 1 end >>= 1 } return st.op(leftRes, rightRes) } func (st *SegmentTree) QueryAll() E { return st.seg[1] } // 二分查询最大的 right 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MaxRight(left int, predicate func(E) bool) int { if left == st.n { return st.n } left += st.size res := st.e() for { for left&1 == 0 { left >>= 1 } if !predicate(st.op(res, st.seg[left])) { for left < st.size { left <<= 1 if predicate(st.op(res, st.seg[left])) { res = st.op(res, st.seg[left]) left++ } } return left - st.size } res = st.op(res, st.seg[left]) left++ if (left & -left) == left { break } } return st.n } // 二分查询最小的 left 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MinLeft(right int, predicate func(E) bool) int { if right == 0 { return 0 } right += st.size res := st.e() for { right-- for right > 1 && right&1 == 1 { right >>= 1 } if !predicate(st.op(st.seg[right], res)) { for right < st.size { right = right<<1 | 1 if predicate(st.op(st.seg[right], res)) { res = st.op(st.seg[right], res) right-- } } return right + 1 - st.size } res = st.op(st.seg[right], res) if right&-right == right { break } } return 0 }