글 읽기 - k번째 숫자 TLE

wwiiiii 7년 전 0

세그먼트 트리에는 각 구간을 정렬시켜 저장하고, 쿼리가 들어오면 해당하는 구간들의 노드 번호를 query 함수로 찾은 다음, 가능한 수의 범위에서 parametric search를 이용해 답을 찾으려고 했는데 TLE가 나네요 ㅠㅠ

query함수 시간복잡도가 logN, count 함수 시간복잡도가 log^2 N, parametric search하는데 log(최대원소값 - 최소원소값)인데 왜 시간 초과가 될까요?

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> container; //raw data 저장 배열, 범위 [1...n]
vector<vector<int> > tree; // 세그먼트 트리, 루트는 1, 왼쪽 자식은 2i, 오른쪽 자식은 2i+1

vector<int> merge(vector<int> a, vector<int> b)
{
	vector<int> res; int aidx = 0, bidx = 0;
	if (a.empty()) return b; if (b.empty()) return a;
	while (aidx < a.size() && bidx < b.size())
	{
		if (a[aidx] < b[bidx]) {
			res.push_back(a[aidx++]);
		}
		else {
			res.push_back(b[bidx++]);
		}
	}
	while (aidx < a.size()) res.push_back(a[aidx++]);
	while (bidx < b.size()) res.push_back(b[bidx++]);
	return res;
}

vector<int> init(int start, int end, int index)
{
	if (start == end) {
		vector<int> temp; temp.push_back(container[start]);
		return tree[index] = temp;
	}
	return tree[index] = merge(
		init(start, (start + end) / 2, index * 2), 
		init((start + end) / 2+1, end, index * 2 + 1)
		);
}

void query(int left, int right, int start, int end, int index, vector<int> & vec)
{
	if (right < start || end < left) {
		return;
	}
	if (left <= start && end <= right) {
		vec.push_back(index);
		return;
	}
	query(left, right, start, (start + end) / 2, index * 2, vec);
	query(left, right, (start + end) / 2 + 1, end, index * 2 + 1, vec);
}

//vec의 크기 O(logN), bound함수 시간 O(logN) => 함수 수행시간 O(log^2 N)
pair<int,int> count(vector<int> & vec, int k, int now)
{
	//lo는 미만인 것 개수, hi는 이하인 것 개수
	int lo = 0, hi = 0;
	for (auto i : vec)
	{
		lo += (int)(lower_bound(tree[i].begin(), tree[i].end(), now) - tree[i].begin());
		hi += (int)(upper_bound(tree[i].begin(), tree[i].end(), now) - tree[i].begin());
	}
	return{ lo,hi };
}

int main()
{
	int l, r, k;
	scanf("%d %d", &n, &m);
	container.resize(n + 10); tree.resize(4 * n + 10);
	for (int i = 1; i <= n; i++) scanf("%d", &container[i]);
	init(1, n, 1);
	for (int i = 0; i < m; i++)
	{
		vector<int> vec;
		scanf("%d %d %d", &l, &r, &k);
		query(l, r, 1, n, 1, vec);
		int left = tree[1].front()-1, right = tree[1].back()+1, mid;
		while (left <= right)
		{
			mid = (left + right) / 2;
			auto cnt = count(vec, k, mid);
			if (cnt.first <= k - 1 && k <= cnt.second)//mid미만인게 k-1개 이하, mid 이하인게 k개 이상이면
			{
				break;			
			}
			else if (cnt.first <= k - 1)//목표값보다 현재값이 더 작은 경우
			{//즉 미만 갯수 <=k-1, 이하 개수 <= k-1
				left = mid + 1;
			}
			else//목표값이 현재값 이상인 경우
			{//미만 개수 >=k, 이하 개수 >=k
				right = mid;
			}	
		}
		printf("%d\n", mid);
	}
}

jaydoubluel 7년 전 4

음수 binary search 할 때에는 조심해야 합니다

if(left + right >= 0) mid = (left + right) / 2; else mid = (left + right - 1)/2;

라던지..

wwiiiii 7년 전 0

고치니까 바로 되네요 ㅎㅎ

ljh6274 7년 전 1

참고하여 도움이 됐습니다. 감사합니다!

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

문제

문제

출처

ICPC

k번째 숫자 TLE

wwiiiii 7년 전 0

jaydoubluel 7년 전 4

wwiiiii 7년 전 0

ljh6274 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말