https://coderun.yandex.ru/problem/security Средняя

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.min
import kotlin.math.max

private const val MAX_TIME = 10000
private const val INF = Int.MAX_VALUE

private lateinit var tree: IntArray
private lateinit var counts: IntArray

private fun buildTree(node: Int, start: Int, end: Int) {
    if (start == end) {
        tree[node] = if (start in 1..MAX_TIME) counts[start] else INF
    } else {
        val mid = start + (end - start) / 2
        buildTree(2 * node, start, mid)
        buildTree(2 * node + 1, mid + 1, end)
        tree[node] = min(tree[2 * node], tree[2 * node + 1])
    }
}

private fun queryTree(node: Int, start: Int, end: Int, l: Int, r: Int): Int {
    if (r < start || end < l || start > end) return INF
    if (l <= start && end <= r) return tree[node]
    val mid = start + (end - start) / 2
    val leftMin = queryTree(2 * node, start, mid, l, r)
    val rightMin = queryTree(2 * node + 1, mid + 1, end, l, r)
    return min(leftMin, rightMin)
}

private fun solve(reader: BufferedReader, writer: BufferedWriter) {
    val line = reader.readLine() ?: ""
    val parts = line.split(" ").filter { it.isNotEmpty() }

    if (parts.isEmpty()) {
        writer.write("Wrong Answer\\n")
        return
    }

    val n: Int
    try {
        n = parts[0].toInt()
    } catch (e: NumberFormatException) {
        writer.write("Wrong Answer\\n")
        return
    }

    if (parts.size != 1 + 2 * n || n < 0) {
        writer.write("Wrong Answer\\n")
        return
    }

    val guards = mutableListOf<Pair<Int, Int>>()
    val delta = IntArray(MAX_TIME + 2) { 0 }
    var hasNonCoveringGuard = false

    try {
        for (i in 0 until n) {
            val indexA = 1 + 2 * i
            val indexB = 1 + 2 * i + 1
            val a = parts[indexA].toInt()
            val b = parts[indexB].toInt()
            guards.add(Pair(a, b))
            if (a >= b) {
                hasNonCoveringGuard = true
            } else {
                delta[a + 1]++
                if (b + 1 <= MAX_TIME + 1) {
                    delta[b + 1]--
                }
            }
        }
    } catch (e: Exception) {
        writer.write("Wrong Answer\\n")
        return
    }

    counts = IntArray(MAX_TIME + 1)
    var currentGuards = 0
    var isFullyCovered = true

    if (n == 0 && MAX_TIME > 0) {
        isFullyCovered = false
    } else if (n > 0) {
        for (t in 1..MAX_TIME) {
            currentGuards += delta[t]
            if (currentGuards <= 0) {
                isFullyCovered = false
                break
            }
            counts[t] = currentGuards
        }
    } else {
        isFullyCovered = false
    }

    if (!isFullyCovered || hasNonCoveringGuard) {
        writer.write("Wrong Answer\\n")
        return
    }

    val treeSize = 4 * (MAX_TIME + 1)
    tree = IntArray(treeSize) { INF }
    buildTree(1, 1, MAX_TIME)

    var allEssential = true
    for ((a, b) in guards) {
        val queryStart = a + 1
        val queryEnd = b
        val minCountInInterval = queryTree(1, 1, MAX_TIME, queryStart, queryEnd)
        if (minCountInInterval > 1) {
            allEssential = false
            break
        }
    }

    if (allEssential) {
        writer.write("Accepted\\n")
    } else {
        writer.write("Wrong Answer\\n")
    }
}

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

    val k = reader.readLine().toInt()
    repeat(k) {
        solve(reader, writer)
    }

    writer.flush()
    reader.close()
    writer.close()
}