Условие

Дано n отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам они принадлежат. Точка x считается принадлежащей отрезку с концами a и b, если выполняется двойное неравенство min(a, b) ≤ x ≤ max(a, b).

Примеры

Ввод: 3 2 0 5 -3 2 7 10 1 6 Вывод: 2 0

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val (n, m) = reader.readLine().split(" ").map(String::toInt)
    val start = IntArray(n)
    val end = IntArray(n)
    val points = Array(m) { Pair(0, 0) }

    // Читаем отрезки
    repeat(n) { i ->
        val (a, b) = reader.readLine().split(" ").map(String::toInt)
        start[i] = minOf(a, b)
        end[i] = maxOf(a, b)
    }

    // Читаем точки
    val pointValues = reader.readLine().split(" ").mapIndexed { index, x -> Pair(x.toInt(), index) }

    // Сортируем отрезки и точки
    start.sort()
    end.sort()
    val sortedPoints = pointValues.sortedBy { it.first }

    val result = IntArray(m)
    var activeSegments = 0
    var i = 0
    var j = 0

    // Обрабатываем точки
    for ((x, index) in sortedPoints) {
        while (i < n && start[i] <= x) {
            activeSegments++
            i++
        }
        while (j < n && end[j] < x) {
            activeSegments--
            j++
        }
        result[index] = activeSegments
    }

    writer.write(result.joinToString(" "))
    writer.newLine()
    writer.flush()
    writer.close()
}