글 읽기 - 대체 뭐가 틀린거죠? 미치겠군요 ㅎㅎ

ajrwk384 5년 전 0

인덱스 트리로 풀었는데( 루트노드 인덱스를 1로)도대체 뭐가 틀린지 모르겠어요,, 질문검색에 있는 테스트케이스까지 포함해서 모두 맞게 나오고,,

트리도 직접 출력해봤는데 노드값들도 다 정상적으로 나오고,, 미치겠네여 ㅎㅎ 고수님들 도와주세요..

#include <iostream>
#define MAX 1000000
using namespace std;

int n, m, k;
long long tree[MAX * 3];

int initTree() {
	for (int i = 1; i <= 3 * n; i++) {
		tree[i] = 0;
	}
	int s = 1;
	while (s < n) s *= 2;
	return s;
}

void update(int node, long long newVal) {
	while (node > 0) {
		tree[node] += newVal;
		node /= 2;	//부모노드 업데이트
	}
}

long long sum(int start, int end) {
	long long r = 0;
	while (start <= end) {
		if (start % 2 == 1) r += tree[start];	//구간합 첫 노드가 홀수번 째(오른쪽 노드라면)
		if (end % 2 == 0) r += tree[end];	//구간합 마지막 노드가 짝수번 째(왼쪽 노드라면) 
		start = (start + 1) / 2;
		end = (end - 1) / 2;
	}
	return r;
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	int firstidx = initTree();	//트리 초기화

	for (int i = 0; i < n; i++) {
		scanf("%d", &tree[firstidx + i]);
	}
	//트리 구성
	for (int i = firstidx - 1; i > 0; i--) {
		tree[i] = tree[i * 2] + tree[i * 2 + 1];
	}
	for (int i = 0; i < m + k; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (a == 1) {
			update(firstidx + b - 1, c - tree[firstidx + b - 1]);
		}
		else {
			printf("%lld\n", sum(firstidx + b - 1, firstidx + c - 1));
		}
	}
	return 0;
}

seico75 5년 전 0

6번째 줄 *3이 충분하지 않은 것으로 알고 있습니다.

모책을 보면 n보다큰 2의 제곱수*2 를 하거나 n*4를 하라고 되어 있네요.

ajrwk384 5년 전 0

n이 최대 1,000,000이고, n보다 큰 2의 제곱수가 1,048,576이라서 2배하면 대략 210만, 넉넉히 3배해서 3백만으로 잡은건데,,

크기에는 아무 이상 없지 않나여?? ㅠㅠ

seico75 5년 전 1

저는 4배로 고쳐서 통과하길래 그문제라고 생각했는데 1000000의 3배니 말씀하신 것이 맞네요.

9라인의 등호가 문제는 안될까요? 실메모리보다 하나더 초기화하는데... 제가 지금 해볼수 없어서 의심되는 거만 말씀드리네요

ajrwk384 5년 전 0

와 맞네여 ㄷㄷ 저걸 왜 못 봤을까요.. 하 뒈져야겠네여..

덕분에 맞았습니다 뜨네여..

감사드립니다. ㅠㅠ

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

문제

문제

출처

ICPC

대체 뭐가 틀린거죠? 미치겠군요 ㅎㅎ

ajrwk384 5년 전 0

seico75 5년 전 0

ajrwk384 5년 전 0

seico75 5년 전 1

ajrwk384 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말