글 읽기 - 뭐가 틀린 걸까요

ktjooho 4년 전 0

세그먼트 트리랑 분할정복으로 풀었는데, 게시판에 있는 반례가 다 맞는데도 계속 33% 에서 틀리다고 뜹니다. 
제가 어떤 점을 놓치고 있는걸까요?.. 
답변 부탁드리겠습니다.
감사합니다.

package com.example.demo

import java.util.*
import kotlin.math.max
import kotlin.math.min

fun main() {
    while(true) {
        val chart = readLine()!!.split(" ").map { it.toLong() }
        val n = chart.size
        if(n == 1 && chart[0] == 0L) break
        val segTree = buildSeg(chart, 0, n - 1)
        var result = 0L
        for(i in 0 until n) {
            val height = chart[i]
            val area = segTree.left(height,i,0) + segTree.right(height,i,n-1) + height
            result = max(result, area)
        }
        println(result)
    }
}

class SegTree {
    var from:Int = 0
    var to:Int = 0
    var minValue:Long = 0
    var leftChildren:SegTree? = null
    var rightChildren:SegTree? = null

    fun right(height:Long, from:Int, to:Int): Long {
        val stack = Stack<Int>()
        stack.push(from + 1)
        stack.push(to)
        var area = 0L
        while(stack.isNotEmpty()) {
            val end = stack.pop()
            val start = stack.pop()
            if(start > end)
                break
            val mid = (start + end) / 2
            val findMin = findMin(start, mid)

            if(findMin >= height) {
                area += (height * (mid - start + 1))
                stack.push(mid + 1)
                stack.push(end)
            } else {
                stack.push(start)
                stack.push(mid - 1)
            }
        }
        return area
    }

    fun left(height: Long, from: Int, to:Int): Long {
        val stack = Stack<Int>()
        stack.push(from - 1)
        stack.push(to)
        var area = 0L
        while (stack.isNotEmpty()) {
            val end = stack.pop()
            val start = stack.pop()
            if(end > start)
                break
            val mid = (start + end) / 2
            val findMin = findMin(mid, start)
            if(findMin >= height) {
                area += (height * (start - mid + 1))
                stack.push(mid - 1)
                stack.push(end)
            } else {
                stack.push(start)
                stack.push(mid + 1)
            }
        }
        return area
    }



    fun findMin(from:Int, to:Int):Long {
        if(from > to)
            return 100000000000009L
        if(this.from == from && this.to == to)
            return minValue
        val mid = (this.from + this.to)/2
        if(to <= mid) {
            return leftChildren!!.findMin(from, to)
        } else if(from > mid) {
            return rightChildren!!.findMin(from, to)
        }

        return min(leftChildren!!.findMin(from, mid), rightChildren!!.findMin(mid+1,to))
    }
}

fun buildSeg(chart:List<Long>, from:Int, to :Int):SegTree {
    val segTree = SegTree()
    val mid = (from + to)/2
    segTree.from = from
    segTree.to = to
    if(from == to) {
        segTree.minValue = chart[from]
        return segTree
    }
    segTree.leftChildren = buildSeg(chart, from, mid)
    segTree.rightChildren = buildSeg(chart, mid + 1, to )
    segTree.minValue = min(segTree.leftChildren!!.minValue, segTree.rightChildren!!.minValue)
    return segTree
}

ktjooho 4년 전 0

입력 부분 처리가 잘못되서, 틀린답이 나왔다고 떴습니다.

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

문제

문제

출처

ICPC

뭐가 틀린 걸까요

ktjooho 4년 전 0

ktjooho 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말