글 읽기 - 금광 파이썬 시간초과 질문

jng6017 3년 전 0

풀이는 c랑 로직이 똑같은거 같은데 python은 맞추신 분들이 없어 질문 드립니다...

파이썬이라 시간초과가 나는건지... 잘모르겠네요 ㅜㅜ

혹시 이 문제가 파이썬이라서 시간초과가 나는거라면

파이썬으로 푸신분들이 없다는 기준 하에서는 그냥 해보고

시간초과 나면 "아 파이썬으로 안되는구나" 하는 방법 뿐인가요?? 파이썬 어렵네요 ㅜㅜ

import bisect
import sys

class node:
    def __init__(self):
        self.tsum, self.lsum, self.rsum, self.msum = 0, 0, 0, 0

    def sum(self, val):
        self.tsum += val
        self.lsum = self.rsum = self.msum = self.tsum
        return self

    def merge(self, left, right):
        self.tsum = left.tsum + right.tsum
        self.lsum = max(left.lsum, left.tsum + right.lsum)
        self.rsum = max(right.rsum, left.rsum + right.tsum)
        self.msum = max(left.rsum + right.lsum, left.msum, right.msum, self.lsum, self.rsum)
        return self

class dot:
    def __init__(self, x, y, w):
        self.x, self.y, self.w = x, y, w

def update(inx, val, node, x, y):
    if y < inx or inx < x:
        return tree[node]
    if x == y:
        return tree[node].sum(val)

    mid = (x + y) >> 1
    return tree[node].merge(update(inx, val, node * 2, x, mid), update(inx, val, node * 2 + 1, mid + 1, y))

N = int(sys.stdin.readline())

dot_list = sorted([dot(*map(int, sys.stdin.readline().split())) for _ in range(N)], key = lambda dot: dot.x)

xs, ys = sorted(list(set(dot.x for dot in dot_list))), sorted(list(set(dot.y for dot in dot_list)))
xs_len, ys_len = len(xs), len(ys)

A = [ [] for _ in range(ys_len) ]
for dot in dot_list:
    x, y = bisect.bisect(xs, dot.x) - 1, bisect.bisect(ys, dot.y) - 1
    A[y].append([x, dot.w])

res = 0
for i in range(ys_len):
    tree = [node() for _ in range(xs_len * 4)]

    for j in range(i, ys_len):
        for k in A[j]:
            update(k[0], k[1], 1, 0, xs_len - 1)
        res = max(tree[1].msum, res)

print(res)

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

문제

문제

출처

ICPC

금광 파이썬 시간초과 질문

jng6017 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말