글 읽기 - python3 제출시 시간초과 나오는데 문제가 어디일까요?

papayetoo 4년 전 0

pypy3으로 하면 통과하는데 python3 제출시 시간초과가 납니다.

느린 부분이 있다는 건데 느린 부분이 어딘지 잘 모르겠습니다.

import math
N,M,K = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(int(input()))
n = len(arr)
treeheight = math.ceil( math.log2(n)) + 1
treesize = 1 << (treeheight+1)  - 1
tree = [0] * treesize


def init(index, start, end):
    # bottom- up 방식
    if start == end:
        tree[index] = arr[start]
    else:
        mid = int( (start + end)/ 2)
        tree[index] = init(index*2+1, start, mid) + init(index*2 +2, mid+1, end)
    return tree[index]

def getsum(node, start, end, left, right):
    
    if left > end or right < start:
        return 0

    if left <= start and end <= right :
        return tree[node]

    mid = int( (start + end) / 2)
    return getsum(node*2 +1, start, mid, left, right) + getsum(node*2+2, mid+1, end, left, right)


def update(node, diff, index, start, end):
    # Top-down 방식
    if index < start or index > end:
        return

    tree[node] += diff

    if start != end :
        mid = int(( start + end) / 2)
        update(node * 2 + 1, diff, index, start, mid)
        update(node * 2 + 2, diff, index, mid + 1, end)

init(0, 0, n-1)
result = []
for _ in range(M + K):
    a, b, c = map(int, input().split())
    if a == 1:
        diff = c - arr[b - 1]
        arr[b - 1] = c
        update(0, diff, b - 1, 0, n -1)
    elif a == 2:
        lst = sorted([b,c])
        result.append(getsum(0, 0, n-1, lst[0] - 1,lst[1]-1))

print(*result, sep='\n')

shg9411 4년 전 0

https://www.acmicpc.net/problem/15552

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

문제

문제

출처

ICPC

python3 제출시 시간초과 나오는데 문제가 어디일까요?

papayetoo 4년 전 0

shg9411 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말