글 읽기 - 파이썬 시간초과입니다. 도와주세요 !!

nexus94 2년 전 0

안녕하세요. 세그먼트트리를 처음 공부해보는 초보입니다.

백준님의 강의 글을 보고 코딩을 해봤는데 5%부터 시간초과가 나네요..

어떤 부분이 문제일까요??

분명 코드는 같아보이는데 ..

도와주세요!!!! 미리 감사합니다 (_ _)

# SEGMENT_TREE_BJ_2042.py

arr = []
seg = []

def update(node, start, end, index, diff):
  if index < start or index > end:
    return
  seg[node] += diff
  if start != end:
    mid = (start + end) // 2
    update(node * 2, start, mid, index, diff)
    update(node * 2 + 1, mid + 1, end, index, diff)

def query(node, start, end, left, right):
  if left > end or right < start:
    return 0
  if left <= start and right >= end:
    return seg[node]
  mid = (start + end) // 2
  return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right)

def init(node, start, end):
  if start == end:
    seg[node] = arr[start]
    return seg[node]
  mid = (start + end) // 2
  seg[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end)
  return seg[node]

if __name__=="__main__":
  N, M, K = map(int, input().split())
  for i in range(0, N):
    arr.append(int(input()))    
  seg = [0 for i in range(0, N*2)]
  init(1, 0, N - 1)
  for _ in range(0, M + K):
    a, b, c = map(int, input().split())
    if a == 1:
      diff = c - arr[b - 1]
      arr[b - 1] = c      
      update(1, 0, N - 1, b - 1, diff)
    else:
      print(query(1, 0, N - 1, b - 1, c - 1))
# 5 2 2
# 1
# 2
# 3
# 4
# 5
# 1 3 6
# 2 2 5
# 1 5 2
# 2 3 5

nexus94 2년 전 0

python3를 pypy3로 하니 맞았습니다.. 참;;

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

문제

문제

출처

ICPC

파이썬 시간초과입니다. 도와주세요 !!

nexus94 2년 전 0

nexus94 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말