글 읽기 - 세그먼트 트리 시간초과의 이유를 모르겠습니다..

kcm0147 3년 전 0

정말 많은 것을 시도 해봤는데 도저히 어디서 시간초과가 나는지 모르겠습니다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{


    static int N,M;
    static long[] minTree;
    static long[] insert;

    public static void main(String[] argv) throws IOException {

        init();

    }

    public static void init() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());


        insert=new long[N];


        for(int i=0;i<N;i++){
            insert[i]=Long.parseLong(br.readLine());
        }

        int x=(int) Math.ceil(Math.log(N)/Math.log(2));
        int size=(int)Math.pow(2,x)*2;
        minTree=new long[size];

        mininit(0,insert.length-1,1);


        for(int i=0;i<M;i++){
            st=new StringTokenizer(br.readLine());
            int left=Integer.parseInt(st.nextToken());
            int right=Integer.parseInt(st.nextToken());
            long minAnswer=minFind(0,insert.length-1,1,left-1,right-1); // left와 right는 값을 구하고 싶은 범
            System.out.printf("%d\n",minAnswer);
        }



    }

    public static long mininit(int left,int right,int node){
        if(left==right)
            return minTree[node]=insert[left];
        int mid=(left+right)/2;

        return minTree[node]=Math.min(mininit(left,mid,node*2),mininit(mid+1,right,node*2+1));
    }



    public static long minFind(int start,int end,int node,int nodeLeft,int nodeRight){
        if(nodeLeft<=start && end<=nodeRight)
            return minTree[node];

        if(end<nodeLeft || nodeRight<start)
            return Long.MAX_VALUE;

        int mid=(start+end) / 2;

        return Math.min(minFind(start,mid,node*2,nodeLeft,nodeRight), minFind(mid+1,end,node*2+1,nodeLeft,nodeRight));

    }

}

djm03178 3년 전 1

System.out.print 계열은 너무 느립니다. BufferedWriter를 사용해서 출력하니 648ms에 통과됩니다.

kcm0147 3년 전 0

아.... System.out.print는 생각도 못하고 계속 다른 곳을 고쳐보고 그랬네요 ...

정말 감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

세그먼트 트리 시간초과의 이유를 모르겠습니다..

kcm0147 3년 전 0

djm03178 3년 전 1

kcm0147 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말