글 읽기 - 시간초과가 계속 뜨는데 원인을 모르겠네요...

ehdwls6856 7년 전 0

for 문이 비록 2중으로 들어가있긴 하지만,

여러가지 방법을 시도했는데 마땅히 생각이 나지 않아서 질문드립니다.

#include <iostream>
#include <cstdio>
using namespace std;

int arr[1000001] = { 0 };
int seq[1000001] = { 0 };
int res[20001] = { 0 };
int n, m, k, a, b, c, total = 0;

void update(int k, int val) {
	seq[k] = val - arr[0];
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		update(i, arr[i]);
	}		
	for (int i = 0; i < m + k; i++) {
		scanf("%d %d %d", &a, &b, &c);		
		if (a > 1) {
			res[i] = arr[0] * (c - b + 1);
			for (int j = b; j <= c; j++) {
				res[i] += seq[j - 1];
			}
			printf("%d\n", res[i]);
		}
		else {
			arr[b - 1] = c;
			update(b - 1, c);
		}
	}	
	return 0;
}

kesakiyo 7년 전 0

2중 for문이지 당연히 TL이 날수밖에 없습니다.

시간복잡도를 계산해 본다면 O(N^2)이 될것이고 N이 꽤 크기 때문에

제 시간내에 못들어오기 때문이죠.

따라서 좀더 고속으로 계산을 할 수 있는 자료구조를 필요로 하게 되는데요.

https://www.acmicpc.net/blog/view/9

이 글을 참고해 보세요.

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

문제

문제

출처

ICPC

시간초과가 계속 뜨는데 원인을 모르겠네요...

ehdwls6856 7년 전 0

kesakiyo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말