글 읽기 - 테스트케이스 추가가 필요한 것 같습니다.

leporem91 7년 전 5

문제 조건이 1<= N,Q <=100000 인데도 불구하고, O(NQ) 복잡도의 알고리즘으로도 패스가 됩니다.

O(NQ) 복잡도 알고리즘은 Q마다 [x,y] 를 더하고, 데이터를 변경하는 방식입니다.

최악의 경우 x,y가 1, 100000 인 Q가 10만번 나오면 모두 시간초과나는 코드들인데도 패스되는 것을 보면

최악의 경우에 대한 테스트케이스가 없는 듯 합니다.

// O(NQ) 로 정답나오는 코드입니다.

#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXN 100005

int arr[MAXN];
int N, Q;
int main(void)
{
	scanf("%d%d", &N, &Q);
	for (int i = 1; i <= N; i++) scanf("%d", &arr[i]);

	for (int i = 0; i < Q; i++)
	{
		int x, y, a, b; scanf("%d%d%d%d", &x, &y, &a, &b);
		long long ans = 0;
		if (x > y) swap(x, y);
		for (int k = x; k <= y; k++) ans += (long long)arr[k];
		printf("%lld\n", ans);
		arr[a] = b;
	}
	return 0;
}

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

문제

문제

출처

ICPC

테스트케이스 추가가 필요한 것 같습니다.

leporem91 7년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말