글 읽기 - 자료형에 따른 시간초과 질문입니다

kengh2472 5년 전 0

인덱스 트리를 이용하여 트리를 업데이트 하고 구간합을 구하는 방법으로 풀었습니다.

처음 int형 tree를 사용하여 제출했을 때는 계속 '틀렸습니다'가 나와서 혹시나 하는 마음에 long long int로 바꾸었을 때 통과하였습니다. 문제에 출력부분에 long long범위를 넘지 않는다 하여 tree내의 값들끼리 덧셈을 하였을 때 int만으로도 가능할 줄 알았는데 아니였습니다.

int를 사용하였을 때에는 시간초과가 나왔는데 틀렸습니다가 아닌 시간초과가 나온 이유가 궁금합니다.

아래코드는 시간초과 코드입니다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N, M, K, arr[2000010], len, st;

void update(int index, int plus) {
	while (index >= 1) {
		arr[index] += plus;
		index /= 2;
	}
}

int sump(int left, int right) {
	int sum = 0;

	while (left <= right) {
		if (left % 2 == 1)
			sum += arr[left];
		if (right % 2 == 0)
			sum += arr[right];
		left = (left + 1) / 2;
		right = (right - 1) / 2;

	}


	return sum;
}

int main(void) {

	scanf("%d %d %d", &N, &M, &K);
	len = 1;
	while (len <= N) {
		len *= 2;
	}
    //make start index, length of tree
	st = len, len *= 2;

	for (int i = st; i < st + N; i++)
		scanf("%d", &arr[i]);
    //init
	for (int i = st - 1; i >= 1; i--) {
		arr[i] = arr[i * 2] + arr[i * 2 + 1];
	}

	for (int t = 0; t < M + K; t++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (a == 1) {
			//update
			update(st + b - 1, c - arr[st + b - 1]);
		}
		else {
			//print sum
			printf("%d\n",sump(st + b - 1, st + c - 1));
		}
	}


	return 0;
}

kengh2472 5년 전 0

다시보니 arr의 범위문제였네요. int로 했을 때 2000010으로 했었습니다. 틀렸습니다가 나오는군요..

물의를 일으켜 죄송합니다..

djm03178 5년 전 1

long long int로 맞은 코드랑 비교해봤는데, int만 long long int로 바뀐 것이 아니고 한 가지 더 바뀐 것이 있었습니다. 바로 arr의 크기입니다.

arr의 크기를 long long int로 정답을 받은 코드와 같이 2500010으로 늘리니, 시간 초과 대신에 틀렸습니다를 받았습니다.

kengh2472 5년 전 0

계산기를 이용하니 크기가 2,097,152까지 나올 수 있었네요. 통과했을 때 에라이 하고 2500000으로 했었습니다.

당연히 N의 2배인줄 알았는데 아니였네요. 감사합니다

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

문제

문제

출처

ICPC

자료형에 따른 시간초과 질문입니다

kengh2472 5년 전 0

kengh2472 5년 전 0

djm03178 5년 전 1

kengh2472 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말