글 읽기 - 세그먼트 트리 시간...

zcx6263 4년 전 0

안녕하세요 아래 소스를 통해서 통과는 받았는데

다른분들에 비해 시간이 너무 느려서

혹시 푸신분들 조언을 얻을수 있을가 해서

질문드립니다.

그리고 똑같은 소스로 타 사이트에 제출하면 시간초과가 납니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {

	static final int max_value = 100000;
	static int N, K;
	static int[] data = new int[max_value+5];
	static ArrayList<Integer>[] tree; 
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		tree = new ArrayList[N*4+5];
		for(int i=1; i<= N*4; i++)
		{
			tree[i] = new ArrayList<>();
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<= N; i++)
		{
			data[i] = Integer.parseInt(st.nextToken());
			update(1, 1, N, i, data[i]);
		}
		
		for(int i=1; i<= N*4; i++)
		{
			if(tree[i].size() == 0) break;
			Collections.sort(tree[i]);
		}
		
		int left = 0, right = 0, k = 0;
		for(int i=1; i<= K; i++)
		{
			st = new StringTokenizer(br.readLine());
			left = Integer.parseInt(st.nextToken());
			right = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			
			int l = -(int)1e9;
			int r = (int)1e9;
			int mid = 0;
			
			while(l <= r)
			{
				mid = (l + r) / 2;
				if(get(1, 1, N, left, right, mid) < k) {
					l = mid + 1;
				}
				else {
					r = mid - 1;
				}
			}
			bw.write(l+"\n");
		}
		bw.flush();
	}
	public static int get(int node, int start, int end, int i, int j, int target)
	{
		int mid = (start + end) / 2;
		if(end < i || j < start) return 0;
		else if(i <= start && end <= j) return upper_bound(node, target);
		else return get(node*2, start, mid, i, j, target) + get(node*2+1, mid+1, end, i, j, target);
	}
	public static void update(int node, int start, int end, int index, int num)
	{
		if(index < start || end < index) return;
		tree[node].add(num);
		if(start == end ) return;
		int mid = (start + end) / 2;
		update(node*2, start, mid, index, num);
		update(node*2+1, mid+1, end, index, num);
	}
	public static int upper_bound(int index, int target)
	{
		int mid = 0, s = 0, e = tree[index].size();
		while(s < e)
		{
			mid = (s + e) / 2;
			if(tree[index].get(mid) <= target) {
				s = mid + 1;
			}
			else {
				e = mid;
			}
		}
		return e;
	}
}

lovinix 4년 전 0

지금 풀이도 충분히 맞다고 생각하지만, 풀이방법을 아예 바꾸는것이 아니라면 머지소트트리를 nlog^2n이 아니라 nlogn에 만든다든가, 세그를 비재귀로 쓰는정도가 있을거같습니다.

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

문제

문제

출처

ICPC

세그먼트 트리 시간...

zcx6263 4년 전 0

lovinix 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말