글 읽기 - 7469번 k번째 수 시간초과의 기준이 궁금합니다.

dustn9401 5년 전 0

11932번 트리와 K번째 수를 풀다가 시간초과가 나서 궁금해서 질문올립니다.

아래 코드는 세그먼트 트리와 이분탐색을 사용한 정답 코드인데요...

시간 제한이 1초라고 나와있긴 한데.. 제가 10만개짜리 난수 배열을 만들어서 시간을 재보니깐 트리를 만드는데에만 6초 이상에

쿼리를 처리하는데는 20초가 넘게 걸립니다.

어떻게 된 걸까요..?

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

int arr[100001], lower, upper, n, m;
vector<int> v;
vector<vector<int>> tree;

void tree_init(int s, int e, int i) {
	if (s == e) {
		tree[i].push_back(arr[s]);
		return;
	}
	int l = i * 2, r = i * 2 + 1;
	tree_init(s, (s + e) / 2, l);
	tree_init((s + e) / 2 + 1, e, r);
	auto lt = tree[l].begin(), rt = tree[r].begin(), le = tree[l].end(), re = tree[r].end();
	while (lt != le || rt != re) {
		if (rt == re)
			tree[i].push_back(*lt), lt++;
		else if (lt == le)
			tree[i].push_back(*rt), rt++;
		else {
			if (*lt < *rt)
				tree[i].push_back(*lt), lt++;
			else
				tree[i].push_back(*rt), rt++;
		}
	}
}
void small_query(int s, int e, int l, int r, int idx, int x)
{
	if (s > r || e < l)
		return;
	if (s >= l && e <= r) {
		lower += distance(tree[idx].begin(), lower_bound(tree[idx].begin(), tree[idx].end(), x));
		upper += distance(tree[idx].begin(), upper_bound(tree[idx].begin(), tree[idx].end(), x));
		return;
	}
	small_query(s, (s + e) / 2, l, r, idx * 2, x);
	small_query((s + e) / 2 + 1, e, l, r, idx * 2 + 1, x);
}
int query(int l, int r, int k) {
	int ret = 0, lo = -1000000000, hi = 1000000000;
	while (true) {
		lower = upper = 0;
		if (lo + hi < 0)
			ret = (lo + hi - 1) / 2;
		else
			ret = (lo + hi) / 2;
		small_query(1, n, l, r, 1, ret);
		if (lower == k - 1 && upper == k)
			break;
		lower < k ? lo = ret : hi = ret;
	}
	return ret;
}
int main()
{
	scanf("%d%d", &n, &m);
	tree.resize(n * 4);
	for (int i = 1; i <= n; i++)
		scanf("%d", arr + i);
	tree_init(1, n, 1);
	for (int i = 0; i < m; i++) {
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		printf("%d\n", query(l, r, k));
	}
	return 0;
}

djm03178 5년 전 1

혹시 디버그 모드로 테스트하신 거라면, 릴리즈 모드로 해보세요.

dustn9401 5년 전 0

아하~~ 릴리즈모드로 하니까 총 0.4초밖에 안걸리네요

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

문제

문제

출처

ICPC

7469번 k번째 수 시간초과의 기준이 궁금합니다.

dustn9401 5년 전 0

djm03178 5년 전 1

dustn9401 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말