글 읽기 - 어느 부분에서 시간 초과를 일으키는지 모르겠습니다(세그먼트 트리)(kotlin)

choiyoujun 3년 전 0

세그먼트 트리로 풀어봤는데,

어느 부분에서 시간 초과가 나오는지 모르겠습니다.

println()이 출력이 느리다하여 BufferedWriter로도 변경해봤습니다.

class SegmentTree(private val arr: LongArray) {
    private val tree = LongArray(arr.size * 2)

    fun init(start: Int, end: Int, node: Int): Long {
        return if (start == end) {
            tree[node] = arr[start]
            tree[node]
        } else {
            val mid = (start + end) / 2
            tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1)
            tree[node]
        }
    }

    fun update(start: Int, end: Int, node: Int, index: Int, diff: Long) {
        if (index !in start..end) return

        tree[node] += diff
        if (start != end) {
            val mid = (start + end) / 2
            update(start, mid, node * 2, index, diff)
            update(mid + 1, end, node * 2 + 1, index, diff)
        }
    }

    fun sum(start: Int, end: Int, node: Int, left: Int, right: Int): Long {
        return if (left > end || right < start) 0
        else if (left <= start && end <= right) tree[node]
        else {
            val mid = (start + end) / 2
            sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right)
        }
    }
}

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val (N, M, K) = readLine().split(" ").map { it.toInt() }

    var arr = longArrayOf()
    repeat(N) {
        arr += readLine().toLong()
    }

    val tree = SegmentTree(arr)
    tree.init(0, arr.size - 1, 1)

    repeat(M + K) {
        val (a, b, c) = readLine().split(" ").map { it.toInt() }
        when (a) {
            1 -> {
                val diff = if (arr[b - 1] <= c) c - arr[b - 1] else c - arr[b - 1]
                tree.update(0, arr.size - 1, 1, b - 1, diff)
            }
            else -> {
                val s = tree.sum(0, arr.size - 1, 1, b - 1, c - 1).toString()
                bw.write(s + "\n")
                bw.flush()
            }
        }
    }
}

scvhero 3년 전 1

update를 필요한 부분에만 하는게 아니라 매번 트리 전체에 대해 수행하는 것 같군요

choiyoujun 3년 전 4

1. 40번째 줄 val arr: LongArray에서 val arr: MutableList<Long>으로 변경 뒤 숫자를 append해서 연산한 결과

"시간 초과" -> "런타임 에러"로 채점 메시지가 바뀌었고

2. 2번째 줄 arr.size * 2를 arr.size * 4로 변경 뒤 채점한 결과

"런타임 에러" -> "틀렸습니다"로 채점메시지가 바뀌었습니다.

3. 51번째 줄에서 내용을

val diff = c.toLong() - arr[b - 1]

arr[b - 1] = c.toLong()

tree.update(0, arr.size - 1, 1, b - 1, diff)

로 변경한 결과

"틀렸습니다" -> "맞았습니다"로 문제 풀이 성공했습니다.

51번째 줄을 변경하기 전, 테스트 케이스로 다음과 같은 값을 입력하면

1 2 2

1 1 1

2 1 1

1 1 2

2 1 1

출력 값으로 1과 3이 나왔지만

수정된 코드로 1과 2로 정상적인 값이 출력됩니다.

class SegmentTree(private val arr: LongArray) {
    private val tree = LongArray(arr.size * 4)

    fun init(start: Int, end: Int, node: Int): Long {
        return if (start == end) {
            tree[node] = arr[start]
            tree[node]
        } else {
            val mid = (start + end) / 2
            tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1)
            tree[node]
        }
    }

    fun update(start: Int, end: Int, node: Int, index: Int, diff: Long) {
        if (index !in start..end) return

        tree[node] += diff
        if (start != end) {
            val mid = (start + end) / 2
            update(start, mid, node * 2, index, diff)
            update(mid + 1, end, node * 2 + 1, index, diff)
        }
    }

    fun sum(start: Int, end: Int, node: Int, left: Int, right: Int): Long {
        return if (left > end || right < start) 0
        else if (left <= start && end <= right) tree[node]
        else {
            val mid = (start + end) / 2
            sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right)
        }
    }
}

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val (N, M, K) = readLine().split(" ").map { it.toInt() }

    var arr = mutableListOf<Long>()
            .apply {
                repeat(N) {
                    add(readLine().toLong())
                }
            }
            .toLongArray()

    val tree = SegmentTree(arr)
    tree.init(0, arr.size - 1, 1)

    repeat(M + K) {
        val (a, b, c) = readLine().split(" ").map { it.toInt() }
        when (a) {
            1 -> {
                val diff = c.toLong() - arr[b - 1]
                arr[b - 1] = c.toLong()
                tree.update(0, arr.size - 1, 1, b - 1, diff)
            }
            else -> {
                val s = tree.sum(0, arr.size - 1, 1, b - 1, c - 1).toString()
                bw.write(s + "\n")
                bw.flush()
            }
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어느 부분에서 시간 초과를 일으키는지 모르겠습니다(세그먼트 트리)(kotlin)

choiyoujun 3년 전 0

scvhero 3년 전 1

choiyoujun 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말