글 읽기 - 뭘 잘못했는지 감이 안 잡힙니다.

drash99 2년 전 0

ps는 처음이라 일단 클래스 만들어서 lazy seg tree 짜 봤는데요, 예제와 게시판의 테케는 다 통과합니다.

하지만 제출하자마자 틀렸습니다가 나오네요. pypy로 실행했고 python3으로는 메모리 초과가 나왔어요.(아마 배열 대신 클래스 쓴 게 큰 거 같아요)

그리고 인터넷에 있는 정답 코드(https://4legs-study.tistory.co...)와 기본적인 슈도 코드는 비슷한 거 같아요.

다른 부분은 findsum/updatesum 부분에서 제 코드는 구간을 쪼개 자녀 노드들로 넘기지만, 저 정답 코드는 쪼개지 않는다는 점?

그 외에는 다른 점이 딱히 없는 거 같아요...

파이썬이다보니 다른 질문에 있었던 오버플로 등의 실수도 없을 거 같고 클래스로 풀었다보니 배열 실수도 나오지는 않을거같아요.

저기 있는 str 메소드 만들어서 확인해보니깐 예제에 대해 lazy 값과 tree의 모양은 잘 유지되는 거 같은데 도대체 뭐가 문제일까요...

---추가---

16975번(원소 출력)은 똑같은 코드로 잘 패스하네요

구간합을 구할때 무언가 잘못한 거 같아요....

16978번도 똑같은 코드로 잘 패스해요

구간합을 구하는 과정에도 문제가 없는 것 같은데 왜 그럴까요 ㅠㅠㅠ

import sys

n, m, k = map(int, input().split())

testarr = []

class lazytree():
    def __init__(self, nums, start, end):
        self.lazy = 0
        self.start = start
        self.end = end
        if start == end:
            self.isleaf = True
            self.sum = nums[start]
        else:
            self.isleaf = False
            self.left = lazytree(nums,start, (start+end)//2)
            self.right = lazytree(nums,(start+end)//2+1, end)
            self.sum = self.left.sum+self.right.sum
    def applylazy(self):
        if self.lazy != 0:
            if not self.isleaf:
                self.left.lazy += self.lazy
                self.right.lazy += self.lazy
            self.sum += self.lazy*(self.end-self.start+1)
            self.lazy = 0
    def findsum(self, start, end):
        self.applylazy()
        if start == self.start and end == self.end:
            return self.sum

        half = (self.start+self.end)//2+1
        if start < half:
            if end < half:
                return self.left.findsum(start,end)
            else:
                return self.left.findsum(start,half-1)+self.right.findsum(half,end)
        else:
            return self.right.findsum(start,end)
    def updatesum(self, start, end, v):
        self.applylazy()
        if start == self.start and end == self.end:
            if not self.isleaf:
                self.left.lazy += v
                self.right.lazy += v
            self.sum += v*(end-start+1)
        else:
            half = (self.start+self.end)//2+1
            if start < half:
                if end < half:
                    self.left.updatesum(start,end,v)
                else:
                    self.left.updatesum(start,half-1,v)
                    self.right.updatesum(half,end,v)
            else:
                self.right.updatesum(start,end,v)
            self.sum = self.left.sum+self.right.sum

    def __str__(self) -> str:
        tmp = f"start: {self.start} end:{self.end} lazy:{self.lazy} sum:{self.sum}"
        if not self.isleaf:
            tmp+='\n'
            tmp += str(self.left)
            tmp+='\n'
            tmp += str(self.right )
        return tmp


nums = []
for _ in range(n):
    nums.append(int(sys.stdin.readline()))

segtree = lazytree(nums,0,len(nums)-1)

for _ in range(m+k):
    line = list(map(int, sys.stdin.readline().split()))
    if line[0] == 1:
        segtree.updatesum(line[1]-1,line[2]-1,line[3])
    else:
        print(segtree.findsum(line[1]-1,line[2]-1))

drash99 2년 전 1

해결했습니다. update할때 자녀노드의 lazy값을 반영안했네요

반례 또한 첨부했습니다.

그리고 혹시 이 문제 푸시는 분들 중에 왜 틀렸는지 이유를 모르겠다면

15967번에 적용해보세요. 문제 자체는 같은 문제고 서브태스크로 채점되어서 어디가 잘못되었는지 알 수 있어요.

8 2 2
1 1 1 1 1 1 1 1
2 3 8 2
1 1 8
2 1 6 -1
1 1 8

---정답
20
14

coffee21 1년 전 1

15967번 문제는 쿼리 번호가 다릅니다.

이 문제에서는 update하는 것이 1이고, 출력하는것이 2이지만 15967번 문제는 그 반대입니다.

그래서 이 문제에서는 위 반례를 다음과 같이 수정해야 합니다.

8 2 2
1 1 1 1 1 1 1 1
1 3 8 2
2 1 8
1 1 6 -1
2 1 8

---정답
20
14

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

문제

문제

출처

ICPC

뭘 잘못했는지 감이 안 잡힙니다.

drash99 2년 전 0

drash99 2년 전 1

coffee21 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말