/* URL: https://yukicoder.me/problems/no/1170 */ package main import ( "bufio" "fmt" "io" "math" "os" "sort" "strconv" ) /*******************************************************************/ var ( n, a, b int X []int S []Segment ) type Segment struct { s, t int } func main() { n, a, b = ReadInt3() X = ReadIntSlice(n) uf := NewUnionFind(n) for i := 0; i < n; i++ { x := X[i] T := X[i+1:] mini := BinarySearch(len(T), -1, func(mid int) bool { return T[mid]-x >= a }) maxi := BinarySearch(-1, len(T), func(mid int) bool { return T[mid]-x <= b }) PrintfDebug("mini: %d, maxi: %d\n", mini+i+1, maxi+i+1) if maxi < mini { continue } uf.Unite(i, mini+(i+1)) S = append(S, Segment{s: mini + (i + 1), t: maxi + (i + 1)}) } sort.SliceStable(S, func(i, j int) bool { if S[i].s < S[j].s { return true } else if S[i].s > S[j].s { return false } else { return S[i].t < S[j].t } }) if len(S) > 0 { // T := []Segment{} // curSeg := S[0] // for i := 1; i < len(S); i++ { // if curSeg.t >= S[i].s { // curSeg = Segment{s: curSeg.s, t: Max(curSeg.t, S[i].t)} // } else { // T = append(T, curSeg) // curSeg = S[i] // } // } // T = append(T, curSeg) // PrintfDebug("%v\n", T) src := [][2]int{} for i := 0; i < len(S); i++ { src = append(src, [2]int{S[i].s, S[i].t}) } T := MergeSegments(src) // for _, seg := range T { for _, seg := range T { // for i := seg.s; i < seg.t; i++ { for i := seg[0]; i < seg[1]; i++ { uf.Unite(i, i+1) } } } for i := 0; i < n; i++ { fmt.Println(uf.CcSize(i)) } } // MergeSegments returns merged source segments. // Segments(Sections) are closed section. // e.g.: [l, r], [l', r'] are merged if r >= l' func MergeSegments(srcSegments [][2]int) [][2]int { _chmax := func(updatedValue *int, target int) bool { if *updatedValue < target { *updatedValue = target return true } return false } res := [][2]int{} isInitialized := false // current segment curL, curR := 0, 0 // sort asc by LEFT coordinate sort.Slice(srcSegments, func(i, j int) bool { return srcSegments[i][0] < srcSegments[j][0] }) for i := 0; i < len(srcSegments); i++ { seg := srcSegments[i] if !isInitialized { curL, curR = seg[0], seg[1] isInitialized = true continue } if curR >= seg[0] { // merge and continue _chmax(&curR, seg[1]) } else { // do not merge, and add it to result res = append(res, [2]int{curL, curR}) curL, curR = seg[0], seg[1] } } if isInitialized { res = append(res, [2]int{curL, curR}) } return res } // Max returns the max integer among input set. // This function needs at least 1 argument (no argument causes panic). func Max(integers ...int) int { m := integers[0] for i, integer := range integers { if i == 0 { continue } if m < integer { m = integer } } return m } // 0-based // uf := NewUnionFind(n) // uf.Root(x) // Get root node of the node x // uf.Unite(x, y) // Unite node x and node y // uf.Same(x, y) // Judge x and y are in the same connected component. // uf.CcSize(x) // Get size of the connected component including node x // uf.CcNum() // Get number of connected components // UnionFind provides disjoint set algorithm. // Node id starts from 0 (0-based setting). type UnionFind struct { parents []int } // NewUnionFind returns a pointer of a new instance of UnionFind. func NewUnionFind(n int) *UnionFind { uf := new(UnionFind) uf.parents = make([]int, n) for i := 0; i < n; i++ { uf.parents[i] = -1 } return uf } // Root method returns root node of an argument node. // Root method is a recursive function. func (uf *UnionFind) Root(x int) int { if uf.parents[x] < 0 { return x } // route compression uf.parents[x] = uf.Root(uf.parents[x]) return uf.parents[x] } // Unite method merges a set including x and a set including y. func (uf *UnionFind) Unite(x, y int) bool { xp := uf.Root(x) yp := uf.Root(y) if xp == yp { return false } // merge: xp -> yp // merge larger set to smaller set if uf.CcSize(xp) > uf.CcSize(yp) { xp, yp = yp, xp } // update set size uf.parents[yp] += uf.parents[xp] // finally, merge uf.parents[xp] = yp return true } // Same method returns whether x is in the set including y or not. func (uf *UnionFind) Same(x, y int) bool { return uf.Root(x) == uf.Root(y) } // CcSize method returns the size of a set including an argument node. func (uf *UnionFind) CcSize(x int) int { return -uf.parents[uf.Root(x)] } // CcNum method returns the number of connected components. // Time complextity is O(n) func (uf *UnionFind) CcNum() int { res := 0 for i := 0; i < len(uf.parents); i++ { if uf.parents[i] < 0 { res++ } } return res } // ChMax accepts a pointer of integer and a target value. // If target value is LARGER than the first argument, // then the first argument will be updated by the second argument. func ChMax(updatedValue *int, target int) bool { if *updatedValue < target { *updatedValue = target return true } return false } func BinarySearch(initOK, initNG int, isOK func(mid int) bool) (ok int) { ng := initNG ok = initOK for int(math.Abs(float64(ok-ng))) > 1 { mid := (ok + ng) / 2 if isOK(mid) { ok = mid } else { ng = mid } } return ok } const ( // General purpose MOD = 1000000000 + 7 // MOD = 998244353 ALPHABET_NUM = 26 INF_INT64 = math.MaxInt64 INF_BIT60 = 1 << 60 INF_INT32 = math.MaxInt32 INF_BIT30 = 1 << 30 NIL = -1 // for dijkstra, prim, and so on WHITE = 0 GRAY = 1 BLACK = 2 ) /*******************************************************************/ /********** bufio setting **********/ func init() { // bufio.ScanWords <---> bufio.ScanLines ReadString = newReadString(os.Stdin, bufio.ScanWords) stdout = bufio.NewWriter(os.Stdout) } /********** FAU standard libraries **********/ //fmt.Sprintf("%b\n", 255) // binary expression /********** I/O usage **********/ //str := ReadString() //i := ReadInt() //X := ReadIntSlice(n) //S := ReadRuneSlice() //a := ReadFloat64() //A := ReadFloat64Slice(n) //str := ZeroPaddingRuneSlice(num, 32) //str := PrintIntsLine(X...) /*********** Input ***********/ var ( // ReadString returns a WORD string. ReadString func() string stdout *bufio.Writer ) func newReadString(ior io.Reader, sf bufio.SplitFunc) func() string { r := bufio.NewScanner(ior) r.Buffer(make([]byte, 1024), int(1e+9)) // for Codeforces r.Split(sf) return func() string { if !r.Scan() { panic("Scan failed") } return r.Text() } } // ReadInt returns an integer. func ReadInt() int { return int(readInt64()) } func ReadInt2() (int, int) { return int(readInt64()), int(readInt64()) } func ReadInt3() (int, int, int) { return int(readInt64()), int(readInt64()), int(readInt64()) } func ReadInt4() (int, int, int, int) { return int(readInt64()), int(readInt64()), int(readInt64()), int(readInt64()) } // ReadInt64 returns as integer as int64. func ReadInt64() int64 { return readInt64() } func ReadInt64_2() (int64, int64) { return readInt64(), readInt64() } func ReadInt64_3() (int64, int64, int64) { return readInt64(), readInt64(), readInt64() } func ReadInt64_4() (int64, int64, int64, int64) { return readInt64(), readInt64(), readInt64(), readInt64() } func readInt64() int64 { i, err := strconv.ParseInt(ReadString(), 0, 64) if err != nil { panic(err.Error()) } return i } // ReadIntSlice returns an integer slice that has n integers. func ReadIntSlice(n int) []int { b := make([]int, n) for i := 0; i < n; i++ { b[i] = ReadInt() } return b } // ReadInt64Slice returns as int64 slice that has n integers. func ReadInt64Slice(n int) []int64 { b := make([]int64, n) for i := 0; i < n; i++ { b[i] = ReadInt64() } return b } // ReadFloat64 returns an float64. func ReadFloat64() float64 { return float64(readFloat64()) } func readFloat64() float64 { f, err := strconv.ParseFloat(ReadString(), 64) if err != nil { panic(err.Error()) } return f } // ReadFloatSlice returns an float64 slice that has n float64. func ReadFloat64Slice(n int) []float64 { b := make([]float64, n) for i := 0; i < n; i++ { b[i] = ReadFloat64() } return b } // ReadRuneSlice returns a rune slice. func ReadRuneSlice() []rune { return []rune(ReadString()) } /*********** Output ***********/ // PrintIntsLine returns integers string delimited by a space. func PrintIntsLine(A ...int) string { res := []rune{} for i := 0; i < len(A); i++ { str := strconv.Itoa(A[i]) res = append(res, []rune(str)...) if i != len(A)-1 { res = append(res, ' ') } } return string(res) } // PrintIntsLine returns integers string delimited by a space. func PrintInts64Line(A ...int64) string { res := []rune{} for i := 0; i < len(A); i++ { str := strconv.FormatInt(A[i], 10) // 64bit int version res = append(res, []rune(str)...) if i != len(A)-1 { res = append(res, ' ') } } return string(res) } // PrintfBufStdout is function for output strings to buffered os.Stdout. // You may have to call stdout.Flush() finally. func PrintfBufStdout(format string, a ...interface{}) { fmt.Fprintf(stdout, format, a...) } /*********** Debugging ***********/ // PrintfDebug is wrapper of fmt.Fprintf(os.Stderr, format, a...) func PrintfDebug(format string, a ...interface{}) { fmt.Fprintf(os.Stderr, format, a...) } // ZeroPaddingRuneSlice returns binary expressions of integer n with zero padding. // For debugging use. func ZeroPaddingRuneSlice(n, digitsNum int) []rune { sn := fmt.Sprintf("%b", n) residualLength := digitsNum - len(sn) if residualLength <= 0 { return []rune(sn) } zeros := make([]rune, residualLength) for i := 0; i < len(zeros); i++ { zeros[i] = '0' } res := []rune{} res = append(res, zeros...) res = append(res, []rune(sn)...) return res }