글 읽기 - 시간초과가 감이 안잡힙니다..알고리듬좀 봐주세요

jhjh9501 4년 전 0

두개의 세그먼트 트리를 사용했습니다.

첫번째 세그먼트 트리의 리프에는 각 좌표에 있는 나무들의 원점으로부터의 거리 합을..

그러니까 나무가 두 개가 4 좌표에 있으면 첫 번째 세그먼트 tree의 리프에는 -> leaf[4] = 4*2

이렇게 되어있고 다른 세그먼트 cnt의 leaf에는 갯수로 -> leaf[4] = 2

이런 식으로 만들어놓고,

각 좌표가 들어올때마다 두 세그먼트 트리에 각각 값을 업데이트 한뒤,

좌표 좌우에서 가격에 해당하는 값을 계산합니다.

구체적으로 첫 번째 세그먼트 트리를 통해 새로 심은 나무 전후에 있는 나무들의 거리 합을 구하고

두 번째 세그먼트 트리를 통해 새로 심은 나무 전후에 있는 나무 갯수를 따로따로구해서 계산해주는 방식인데...

시간초과가 납니다. ㅠㅠ왜날까요 ㅠㅠㅠㅠㅠㅠ

import sys
import math

N = int(sys.stdin.readline())
DATA_INDEX = 2 ** (math.ceil(math.log(200000, 2))) - 1
MAX_SIZE = 2 ** (math.ceil(math.log(200000, 2)) + 1) - 1
cnt = [0] * MAX_SIZE
tree = [0] * MAX_SIZE


def segsum(arr, L, R, nodeNum, nodeL, nodeR):
    if R == -1 : return 0
    if L > nodeR or R < nodeL : return 0
    if L <= nodeL and nodeR <= R : return arr[nodeNum]
    mid = (nodeL+nodeR)//2
    return segsum(arr, L, R, nodeNum*2 +1, nodeL, mid) + segsum(arr, L, R, nodeNum*2 + 2, mid+1, nodeR)


def update(arr, i, val):
    i += DATA_INDEX
    arr[i] += val
    while i>0:
        i = (i-1)//2
        arr[i] = arr[i*2+1] + arr[i*2+2]

total = 1
for i in range(N):
    x = int(sys.stdin.readline())
    cost = 0
    if i == 0:
        update(tree, x, x)
        update(cnt, x, 1)
        continue
    update(tree, x, x)
    update(cnt, x, 1)
    cost -= (segsum(tree, 0, x-1, 0, 0, DATA_INDEX) ) % 1000000007
    cost += (segsum(cnt, 0, x-1, 0, 0, DATA_INDEX) * x ) % 1000000007
    cost += (segsum(tree, x+1, DATA_INDEX, 0, 0, DATA_INDEX) ) % 1000000007
    cost -= (segsum(cnt, x+1, DATA_INDEX, 0, 0, DATA_INDEX) * x) % 1000000007
    print(i, cost)
    total = (total*cost) % 1000000007

print(total)

djm03178 4년 전 0

이 코드에서 40번째 줄만 지우고 내봤는데 5912ms로 통과합니다.

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

문제

문제

출처

ICPC

시간초과가 감이 안잡힙니다..알고리듬좀 봐주세요

jhjh9501 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말