Scanline ошибка в тестах
Код валится на одном закрытом тесте, в голову ничего не лезет и ии-шки не могут привести пример данных на котором бы код ломался, подскажите в чем ошибка.
Дано n отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам они принадлежат. Точка x считается принадлежащей отрезку с концами a и b, если выполняется двойное неравенство min(a, b) ≤ x ≤ max(a, b).
type event struct {
x, t, idx int
}
func main() {
var n, m int
fmt.Scan(&m, &n)
events := make([]event, 0, m*2+n)
//заполнение координат точек начала и конца отрезков
for i := 0; i < m; i++ {
var a, b int
fmt.Scan(&a, &b)
events = append(events, event{a, 1, -1})
events = append(events, event{b, -1, -1})
}
//заполнение координат точек
for i := 0; i < n; i++ {
var dot int
fmt.Scan(&dot)
events = append(events, event{x: dot, t: 0, idx: i})
}
// сортировка по координатам и типу(начало или конец отрезка или точка)
sort.Slice(events, func(i, j int) bool {
if events[i].x == events[j].x {
return events[i].t > events[j].t
}
return events[i].x < events[j].x
})
cnt := 0
answer := make([]int, n)
for _, e := range events {
if e.t == 0 {
answer[e.idx] = cnt
}
cnt += e.t
}
for i := range answer {
fmt.Print(answer[i], " ")
}
}
Ответы (2 шт):
Запись min(a, b) ≤ x ≤ max(a, b) подразумевает что концы отрезка во входных данных неупорядочены и возможна ситуация когда a > b. Ваш код предполагает что a ≤ b. Это может быть причиной проблем.
По условию задачи
Дано n отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам они принадлежат.
Вы же аллоцируете m отрезков и n точек. Вполне возможно, что вы неправильно считываете пары a,b и fmt.Scan заполняет координаты нулями. Надо проверять возвращаемые значения fmt.Scan