글 읽기 - 파이썬 시간초과.. (주석 있음)

lem0nad3 2년 전 0

A_i를 최솟값으로 가지는 인덱스 구간 [l, r]를 찾기 위해 i를 기준으로 왼쪽, 오른쪽 각각 이분탐색을 진행하여 A_i보다 작지 않은 값만이 나오는 가장 긴 구간을 찾는 방식으로 코드를 작성했습니다.

구간 최솟값은 세그트리를 통해 찾도록 했습니다.

각각의 A_i에 대하여 (N)

가장 멀리 갈수 있는 인덱스를 이분탐색으로 찾기(lg N)

그 인덱스부터 A_i까지의 최솟값 찾기(세그트리를 이용했으므로 lg N)

시간복잡도는 O(Nlg²N)으로 보이고, N은 최대 10만이므로 충분(=25,600,000) 하다고 생각했는데

1퍼 시간초과면 이해를 하겠는데 빠른속도로 잘 채점이 되다가 36퍼에서 막히더니 시간초과가 뜨네요..

seg = [0 for _ in range(4040404)]
def init(n, s, e): #세그트리 초기화
    if s == e:
        seg[n] = a[s - 1]
        return seg[n]
    m = (s + e) // 2
    seg[n] = min(init(n * 2, s, m), init(n * 2 + 1, m + 1, e))
    return seg[n]

def getMin(n, s, e, l, r): #구간 [l, r]에서 최솟값 찾기
    if e < l or r < s:
        return 10000000000000000
    if l <= s and e <= r:
        return seg[n]
    m = (s + e) // 2
    return min(getMin(n * 2, s, m, l, r), getMin(n * 2 + 1, m + 1, e, l, r))

pre = [0 for _ in range(1010101)]
n = ip() # int(input())
a = lmip() # list(map(int, input().split()))

init(1, 1, n)
for i in range(n): #Prefix Sum 배열 갱신
    pre[i + 1] = pre[i] + a[i]

ans = 0
for i in range(n):
    lo = i + 1 #배열 a는 인덱스 시작이 0이지만, 세그트리는 1부터 시작이므로 i + 1로 넣어줌
    hi = n
    while lo <= hi: #오른쪽으로 갈 때, 가장 멀리갈 수 있는 인덱스 찾기
        mid = lo + hi >> 1
        x = getMin(1, 1, n, i + 1, mid)
        if x >= a[i]: #가능하면 범위 확장 가능: 오른쪽으로 가기
            lo = mid + 1
        else: #불가능하므로: 범위 축소
            hi = mid - 1
    ridx = hi

    lo = 1
    hi = i + 1
    while lo <= hi: #왼쪽으로 갈 때, 가장 멀리갈 수 있는 인덱스 찾기
        mid = lo + hi >> 1
        x = getMin(1, 1, n, mid, i + 1)
        if x < a[i]: #불가능하므로: 범위 축소
            lo = mid + 1
        else: #가능하므로 범위 확장: 왼쪽으로 늘리기
            hi = mid - 1
    lidx = lo

    ans = max(ans, (pre[ridx] - pre[lidx - 1]) * a[i]) #답 갱신
print(ans)

lem0nad3 2년 전 1

파이썬이라 당했네요^^

c++로 하니까 통과했습니다

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

문제

문제

출처

ICPC

파이썬 시간초과.. (주석 있음)

lem0nad3 2년 전 0

lem0nad3 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말