글 읽기 - 시간초과 이유가 이것인지 좀 봐주세요

kkw564 7년 전 0

memcpy(tmp, arr + start - 1, (end - start + 1)*sizeof(int));

이부분에서 O(n^2)이 되기때문에 시간초과인건가요? 꼭 seg tree로 짜야되고 일반적인 다른 방법은 없을지 궁금합니다.

#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

int arr[100001];
int tmp[100001] = { 0, };

bool comp(int const& a, int const& b) {
	return a < b;
}

int main()
{
	int n, m;
	int start, end, ret;
	int k = 0;

	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &start, &end, &ret);
		
		memcpy(tmp, arr + start - 1, (end - start + 1)*sizeof(int));

		std::sort(tmp, tmp + (end - start + 1), comp);

		printf("%d\n", tmp[ret - 1]);
	}
}

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

문제

문제

출처

ICPC

시간초과 이유가 이것인지 좀 봐주세요

kkw564 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말