글 읽기 - 시간초과의 이유가 무엇일까요..?

tjswns1542 3년 전 0

나름 나이스하게 코드 짰다고 생각했는데ㅠㅠ

도대체 어디서 시간초과가 나는 건지 못찾겠네요..

고수님들의 답변 기다리고 있겠습니다.

미리 감사합니다.

#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

// 숫자 전체 개수가 N개라면
// 배열의 크기는 N보다 크면서 가장 작은 2의 거듭제곱(s)이 
// N개가의 숫자가 배열의 들어갈  시작위치이다.
ll tree[3000000];
int N, M, K;
int s;
void makeTree() {
	for (int i = s - 1; i > 0; i--) {
		tree[i] = tree[i * 2] + tree[i * 2 + 1];
	}
}
void updateTree(int b, int c) {
	int curIdx = s + b - 1;
	int addedValue = c - tree[curIdx];
	tree[curIdx] = c;

	while (curIdx != 1) {
		
		curIdx /= 2;
		tree[curIdx] += addedValue;
	}

}

ll getPsum(int start, int end) {
	ll psum = 0;
	start = s + start - 1;
	end = s + end - 1;
	while (start != end) {
		if (start % 2 == 1) {
			psum += tree[start];
			start++;
		}

		if (end % 2 == 0) {
			psum += tree[end];
			end--;
		}
		start /= 2; end /= 2;
	}
	psum += tree[start];
	return psum;

}
int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M >> K;
	s = 1;

	while (s < N) {
		s *= 2; // 배열상 시작위치 찾기.
	}
	for (int i = 0; i < N; i++) {
		cin >> tree[s + i];
	}

	makeTree();

	int a, b, c;
	for (int i = 0; i < M + K; i++) {
		cin >> a >> b >> c;
		if (a == 1) {
			updateTree(b, c);
		}
		else {
			ll result = getPsum(b, c);
			cout << result << endl;
		}
	}

}

seico75 3년 전 1

문제 상황의 입력입니다.

tjswns1542 3년 전 0

답변감사드립니다!

이런것도 못발견하다니 ㅠㅠㅜ

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

문제

문제

출처

ICPC

시간초과의 이유가 무엇일까요..?

tjswns1542 3년 전 0

seico75 3년 전 1

tjswns1542 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말