글 읽기 - 테스트케이스 추가(?)

cbs0615 6년 전 1

O(nm)으로는 문제가 풀리지 않을 것 같아서,

여러 시도 끝에 겨우 문제를 풀었습니다.

그런데 다른 사람 코드를 보니 O(nm)으로도 테스트케이스를 통과하더군요.

생각해보니까 n이 10만이고 m이 5천이니, 간단하게 짠다면 통과 가능하다고 생각했습니다.

그런데 그런 코드들 중에 다음과 같은 테스트 케이스를 시간 내에 처리하지 못하는 코드가 있는 것 같습니다.

int n = 100000;
int m = 5000;

vector<int> arr(n);
for(int i = 0;i < n;i ++){
    arr[i] = i;
}

for(int i = 0;i < m;i ++){
    int s = 1, e = n; k = n;
   
    // k-th element query
}

startlink 6년 전 0

데이터를 추가했습니다.

djm03178 6년 전 0

음 몇몇 코드들을 보니 여전히 O(nlgn + nm)이 뚫리긴 하는 거 같습니다. 더 최악의 케이스가 없고 시간 제한을 더 줄이는 것이 좀 그렇다면 어쩔 수 없겠지만요.

s7d8f9 6년 전 0

정확하게 이해가 안되서 그런데, 그렇다면 5억의경우 코드를 간단하게 짜게된다면 1초안에 통과가 가능하다는 의미인가요?

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

문제

문제

출처

ICPC

테스트케이스 추가(?)

cbs0615 6년 전 1

startlink 6년 전 0

djm03178 6년 전 0

s7d8f9 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말