글 읽기 - 세그먼트트리, 5%에서 틀렸다고 나옵니다

ks96ks 3년 전 0

코틀린이지만 자바나 c++쓰시는 분들도 코드 보시기엔 크게 안어렵다고 생각합니다

질문게시판에 있는 예제들해봐도 통과하는데 5%에서 틀렸다고 나오네요 ㅠㅠ

import java.util.*
import kotlin.math.pow

fun main() = with(Scanner(System.`in`)) {
    val N = nextInt(); val M = nextInt(); val K = nextInt()
    val arr = LongArray(1_000_001)
    val tree = LongArray(4_000_004)
    for(i in 0 until N)
        arr[i] = nextLong()

    val list = Array(M + K) { Data(nextInt(), nextInt(), nextLong()) }

    var depth = 1
    while(2.0.pow(depth) < N)
        depth++
    depth = 2.0.pow(depth).toInt()

    fun init() {
        for(i in 0 until N)
            tree[depth + i] = arr[i]

        for(i in (1 until depth).reversed())
            tree[i] = tree[i * 2] + tree[i * 2 + 1]
    }

    fun update(idx : Int, num : Long) {
        var i = idx + depth - 1
        tree[i] = num
        while(i > 1) {
            i /= 2
            tree[i] = tree[i * 2] + tree[i * 2 + 1]
        }
    }

    fun sum(left : Int, right : Int, nodeNum : Int, nodeL : Int, nodeR : Int) : Long {
        if(right < nodeL || nodeR < left)
            return 0
        if(left <= nodeL && nodeR <= right)
            return tree[nodeNum]
        val mid = (nodeL + nodeR) / 2
        return sum(left, right, nodeNum * 2, nodeL, mid) + sum(left, right, nodeNum * 2 + 1, mid + 1, nodeR)
    }

    init()

    fun debug() {
        var cur = 2
        for(i in 1 until depth * 2) {
            if(i % cur == 0) {
                cur *= 2
                println()
            }
            print("${tree[i]} ")
        }
    }

    for(dt in list) {
        if(dt.a == 1) {
            update(dt.b, dt.c)
        }
        else {
            val l = dt.b
            val r = dt.c.toInt()
            println(sum(l, r, 1, 1, N))
        }
    }

}

data class Data(val a : Int, val b : Int, val c : Long)

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

문제

문제

출처

ICPC

세그먼트트리, 5%에서 틀렸다고 나옵니다

ks96ks 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말