글 읽기 - 이 코드 반례 부탁드립니다..

kth990303 3년 전 0

제가 공부가 부족한 탓인지, update를 이렇게 짜보고 제출하였더니 WA가 뜨는데 이유를 모르겠습니다.

3 5

1 1 3

1 3 2

1 3 5

1 2 4

0 1 2

ans: 7

등 이러한 경우에 디버깅 결과의 tree 배열 및 결과 또한 잘 나오는 듯하고,

long long 처리 및 b>c일 때 swap 처리 또한 잘해주었는데,

어디서 틀린건지 모르겠네요.

init은 어차피 처음엔 tree의 모든 원소가 0이어서 하지 않았습니다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a[1000001];
ll tree[4000004];
int N, M;
ll query(int node, int left, int right, int s, int e) {
	if (e < left || right < s)
		return 0;
	if (left <= s && e <= right)
		return tree[node];
	int mid = (s + e) / 2;
	return query(node * 2, left, right, s, mid)
		+ query(node * 2 + 1, left, right, mid + 1, e);
}
ll update(int node, int s, int e, int idx) {
	if (idx<s || idx>e)
		return a[s];
	if (s == e)
		return tree[node] = a[s];
	int mid = (s + e) / 2;
	return tree[node] = update(node * 2, s, mid, idx) +
		update(node * 2 + 1, mid + 1, e, idx);
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> M;
	while (M--) {
		int ch, b, c;
		cin >> ch >> b >> c;
		if (ch == 0) {
			if (b > c) swap(b, c);
			cout << query(1, b, c, 1, N) << "\n";
		}
		else {
			a[b] = c;
			update(1, 1, N, b);
		}
	}
}

kth990303 3년 전 0

해결됐습니다 update 함수에서 인덱스가 벗어날 때의미없는 값을 반환하고 있었어요ㅠㅠ

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

문제

문제

출처

ICPC

이 코드 반례 부탁드립니다..

kth990303 3년 전 0

kth990303 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말