pl0892029   9년 전

소스 내에 STL thread를 사용하려고 넣었더니 다음과 같은 에러가 납니다.

terminate called after throwing an instance of '

무슨 일일까요...

https://www.acmicpc.net/coding/view/5424

h0ngjun7   9년 전

소스 코드를 올려주시면 답변드리는데 도움이 될 것 같습니다.

pl0892029   9년 전

@hongjun7

사실 문제를 푸는데 쓰레드를 써서 해결하려고 하는 방법은 좋은 방법이 아니지요..

현재 배열의 힘 문제를 풀고 있으며, 작성한 아이디어는 다음과 같은 커팅방법입니다.

"임의의 쿼리 [L,R]은 L' <= L 이고, R <= R'인 다른 쿼리 [L',R']에 포함되는 형태나, L <= L'이고 R <= R'인 다른 쿼리 [L',R']에 연속되는 형태를 지니게 된다."

따라서 임의의 쿼리를 잡고, 그리디하게 두 개의 쿼리 집합을 뽑아내서 (포함관계일 때와, L <= L' 이고 R <= R'인 형태일 때) 두 순열 중 원소의 갯수가 많은 쪽을 선택해서 해당 집합들을 이용해 O(N)으로 답들을 구해내고,이 원소들을 제거하여 쿼리들의 답을 채우는 방식을 사용했습니다.

시간복잡도는 O( 반복횟수 * (쿼리의 수 + 원소들의 수 + memset으로 값들의 갯수를 0으로 초기화) ) 만큼 걸리는 걸로 생각합니다.

이 때 반복횟수는 공식 데이터를 다운받아서 모두 실행해본 결과 700이 초과되지 않았습니다.

소스는 위에 수정하여 올리겠습니다... 상수가 많이 붙어서 이런 문제가 발생하는 건가요? ㅠ.ㅠ

채점중 1퍼에서 오르지도 않고 시간초과로 바뀌어버리네요...

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