글 읽기 - 90%에서 시간초과

chlee2734 2년 전 0

안녕하세요.

14504 문제를 풀어 보았습니다.

비쥬얼 스튜디오에서는 입력 예시대로 입력 하였을 때 올바른 출력 결과가 나옵니다.

그런데 제출을 하니 계속 90%에서 시간 초과가 발생하여 질문드립니다.

입력 받을 때 문제가 있는 것 같아 2차원 배열 동적할당, 문자열 파싱 후 atoi, 하드 코딩(if 문 분기) 등을 시도 해 보았고

연산 부분의 경우 함수 정의 호출을 시도해 보았는데 다 비쥬얼에선 잘만 돌아가는데 제출 하면 시간 초과

or 컴파일 에러가 나타납니다.

함께 고민해주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>

using namespace std;


int main()
{
	int N, M;
	int i, j;
	int count = 0;

	scanf("%d", &N);
    
    int *A = new int[N];

	for (i = 1; i <= N; i++)
		scanf("%d", &A[i]);

	scanf("%d", &M);
    int **Query = new int*[M];
    
    for (i = 0; i < M; i++)
	{
		Query[i] = new int[4];
	}


	for (i = 0; i < M; i++)
	{
		scanf("%d", &Query[i][0]);
       int cnt = (Query[i][0] % 2) + 3;
		
			for (j = 1; j < cnt; j++)
			{
				scanf("%d", &Query[i][j]);
			}
		

	}

	for (i = 0; i < M; i++)
	{
		if (Query[i][0] == 1)
		{
			count = 0;
			for (j = Query[i][1]; j <= Query[i][2]; j++)
			{
				if (A[j] > Query[i][3])
					count++;
			}
			printf("%d\n", count);
		}
		else
		{
			A[Query[i][1]] = Query[i][2];
		}
	}
    for (i = 0; i < M; i++)
		delete[]Query[i];
	delete[]Query;
    	delete[]A;
	return 0;
}

jh05013 2년 전 0

입력 크기가 10만이라서 단순 구현으로는 시간초과를 피할 수 없습니다. 90%까지 간다는 게 신기하네요.

수열과 쿼리 문제들은 훨씬 효율적인 알고리즘이나 자료구조를 사용해야 풀 수 있습니다.

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

문제

문제

출처

ACM-ICPC

90%에서 시간초과

chlee2734 2년 전 0

jh05013 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말