글 읽기 - 파이썬 시간초과 질문드립니다.

pepper_mis 2년 전 0

시간초과가 나는데 어디서 시간을 줄여야 할지 전혀 알수가 없네요...

세그먼트 트리를 리스트로 만들어서 시간이 오래걸린걸까요?

https://www.acmicpc.net/source... 여기 코드랑 제 코드가 차이가 뭘까요...??

import sys
input = sys.stdin.readline

def tree_init(start, end, node):
    if start == end:
        tree[node] = [start, start]
    else:
        mid = (start+end)//2
        left_node = tree_init(start, mid, node*2)
        right_node = tree_init(mid+1, end, node*2+1)
        tree[node] = [left_node[0], right_node[1]]
    return tree[node]

def tree_find(start, end, node, left, right):
    if start > right or end < left:
        return True
    if start >= left and end <= right:
        return left <= tree[node][0] and right >= tree[node][1]
    mid = (start+end)//2
    left_result = tree_find(start, mid, node*2, left, right)
    right_result = tree_find(mid+1, end, node*2+1, left, right)
    return left_result and right_result

def tree_update(start, end, node, index, num):
    if start > index or end < index:
        return tree[node]
    if start == end:
        tree[node] = [num, num]
    else:
        mid = (start+end)//2
        left_node = tree_update(start, mid, node*2, index, num)
        right_node = tree_update(mid+1, end, node*2+1, index, num)
        tree[node] = [min(left_node[0], right_node[0]), max(left_node[1], right_node[1])]
    return tree[node]

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    arr = [i for i in range(N)]
    tree = [0] * (N*4)
    tree_init(0, N-1, 1)
    for i in range(K):
        Q, A, B = map(int, input().split())
        if Q == 0:
            tree_update(0, N-1, 1, A, arr[B])
            tree_update(0, N-1, 1, B, arr[A])
            arr[A], arr[B] = arr[B], arr[A]
        else:
            if tree_find(0, N-1, 1, A, B):
                print('YES')
            else:
                print('NO')

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

문제

문제

출처

ICPC

파이썬 시간초과 질문드립니다.

pepper_mis 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말