글 읽기 - 정해인데 틀리고 있는 거 같아요 ㅜㅜ,,

ploffer11 5년 전 0

최소최대 세그트리 사용했는데 도대체 왜 tle죠..?

update query 모두 O(log n)에 작동하는데..

제가 봤을땐 테스트케이스가 왜 20개씩이나 되서 그런거 같은데 왜 이렇게 많이 들어오는지..

정답자에 pypy3분 있던데 도대체 어떻게 통과받으신지 모르겠습니다.

제가 어느부분에서 틀렸을까요?

import sys 
sys.setrecursionlimit(300000)
read = lambda : map(int, sys.stdin.readline().split())
write = lambda x : sys.stdout.write(["NO\n", "YES\n"][x])
INF = float('INF')

class SegmentTree:
  def __init__(self):
    self.n, self.q = read()
    self.arr = list(range(self.n))
    self.tree = [ [INF, -INF] for i in range(4*self.n) ]
    self.init(1, 0, self.n-1)

  def compare(self, a, b):
    return [
      min(a[0], b[0]), max(a[1], b[1]) 
    ]

  def init(self, node, s, e):
    if s == e:
      self.tree[node] = [self.arr[s], self.arr[s]]
      return
    m = (s + e) // 2

    self.init(2*node, s, m)
    self.init(2*node+1, m+1, e)

    self.tree[node] = self.compare(
      self.tree[2*node], self.tree[2*node+1]
    )

  def update(self, node, s, e, i, n):
    if not s <= i <= e:
      return
    if s == e:
      self.tree[node] = [n, n]
      return
    m = (s + e) // 2

    self.update(2*node, s, m, i, n)
    self.update(2*node+1, m+1, e, i, n)

    self.tree[node] = self.compare(
      self.tree[2*node], self.tree[2*node+1]
    )

  def query(self, node, s, e, l, r):
    if s > r or e < l:
      return [INF, -INF]
    
    if l <= s and e <= r:
      return self.tree[node]

    m = (s + e) // 2
    return self.compare(
      self.query(2*node, s, m, l, r),
      self.query(2*node+1, m+1, e, l, r),
    )

  def solve(self):
    for q in range(self.q):
      query, a, b = read()

      if query:
        m1, m2 = self.query(1, 0, self.n-1, a, b)
        write(a==m1 and b==m2)

      else:
        self.update(1, 0, self.n-1, a, self.arr[b])
        self.update(1, 0, self.n-1, b, self.arr[a])

        self.arr[a], self.arr[b] = self.arr[b], self.arr[a]
    

for t in range(int(input())):
  Tree = SegmentTree()
  Tree.solve()

yukariko 5년 전 0

pypy가 재귀에선 시간이 많이 느리게 나오는걸로 알고있습니다.

ploffer11 5년 전 0

지금까지 pypy3로 세그트리 문제들 많이 AC 받았는데 이 문제는 조금 너무한 거 같아요

n k도 큰데 테스트케이스가 왜 20개씩이나 들어오는지..

yukariko 5년 전 0

세그트리는 비재귀 구현도 있습니다.

비재귀가 재귀보다 상당히 빠르기때문에 정답을 받을 수 있을것으로 보입니다.

yukariko 5년 전 0

참고로 C/C++로 풀어도 시간이 빠듯한 문제가 많이 있습니다.

상대적으로 느린 언어를 사용할때는 그 점을 감안 하셔야 합니다.

비정상적으로 시간제한이 적은 문제는 시간제한 변경 요청하시면 올려주실거구요.

이 문제는 그정도는 아닌거같고 간단한 최적화를 통해 해결이 가능해보입니다.

ploffer11 5년 전 0

비재귀 테크닉 어려워보여서 안쓰고있었는데 이번 기회에 배워봐야겠네요 감사합니다!!

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

문제

문제

출처

ICPC

정해인데 틀리고 있는 거 같아요 ㅜㅜ,,

ploffer11 5년 전 0

yukariko 5년 전 0

ploffer11 5년 전 0

yukariko 5년 전 0

yukariko 5년 전 0

ploffer11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말