글 읽기 - 어디서 틀린건지 모르겠습니다...5%에서 틀립니다..

dlrjs2360 1년 전 0

반례는 다 맞는데 문제 예시에서 17 14가 나오네요...

뭐가 틀린건지 모르겠습니다.

다른분들은 차이를 연관노드들에 더해주던데 저는 바꿔야할 노드 자체를 바꾸고 상향하면서 합을 구했습니다.

제 머리로는 맞는거 같은데 왜 안되는지 모르겠습니다...흑..

def update(node, idx, val, left, right):
    if idx < left or idx > right:
        return segment_tree[node]
    if left == right:
        segment_tree[node] = val
        return segment_tree[node]

    mid = (right+left)//2
    left_val = update(2*node,idx,val,left,mid)
    right_val = update(2*node+1,idx,val,mid+1,right)
    segment_tree[node] = merge(left_val,right_val)
    return segment_tree[node]

def query(node,start,end,left,right):
    if end < left or start > right:
        return 0
    if start <= left and right <= end:
        return segment_tree[node]

    mid = (right+left)//2
    left_val = query(node*2,start,end,left,mid)
    right_val = query(node*2+1,start,end,mid+1,right)
    return merge(left_val,right_val)

def build(node,left,right):
    if left == right: # 단말 노드 처리
        segment_tree[node] = arr[left]
        return segment_tree[node]

    mid = (right+left)//2
    left_val = build(2*node,left,mid)
    right_val = build(2*node+1,mid+1,right)
    segment_tree[node] = merge(left_val,right_val)
    return segment_tree[node]

def merge(left,right):
    return left+right

n,m,k = map(int,input().split())
arr = []
for _ in range(n):
    arr.append(int(input()))

segment_tree = [0] * (n*4+1)
build(1,0,n-1)

for _ in range(m+k):
    a,b,c = map(int,input().split())
    if a == 1: # b번째 수를 c로 바꾼다.
        update(1,b,c,0,n) # update(idx, val, node, left, right)
    if a == 2: # b번째부터 c번째까지의 합을 구한다.
        print(query(1,0,n,b,c)) # query(node,start,end,left,right)

kwakws0627 1년 전 1

45번째 줄 보니까 0-base 로 구현하셨네요 (arr 인덱스가 0 ~ n - 1)

문제에서는 arr 이 1-base 입니다 (arr 인덱스가 1 ~ n)

50번째 줄에서 b번째 수를 c로 바꾼다라고 하셨는데요,

0-base 에서는 b - 1 번째 수를 바꿔야 합니다. (게다가 left, right 범위도 0 ~ n - 1 이 되어야 합니다.)

52번째 줄 또한 비슷한 이유로 좀 바꿔야 겠네요.

게다가 52번째 줄에서 start, end, left, right 파라미터 전달하는 순서가 좀 이상한 거 같습니다.

또한, 제 경험상 이런 종류의 문제는 빠른 입출력 받지 않으면 시간 초과가 나는 경우가 많더라고여

빠른 입출력은 아래 문제에서 확인 부탁 드립니다.

https://www.acmicpc.net/proble...

dlrjs2360 1년 전 1

감사합니다. 좀 헷갈리다보니 뒤죽박주 된 것 같습니다. 말씀해주신 부분 잘 확인해보겠습니다!

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

문제

문제

출처

ICPC

어디서 틀린건지 모르겠습니다...5%에서 틀립니다..

dlrjs2360 1년 전 0

kwakws0627 1년 전 1

dlrjs2360 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말