Guest User

boj1933

a guest
Apr 14th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.95 KB | None | 0 0
  1. #1933
  2. import sys
  3. from heapq import *
  4. input = sys.stdin.readline
  5.  
  6. pts, strt, end, sol = set(), {}, {}, []
  7.  
  8. for _ in range(int(input())):
  9.     l, h, r = map(int, input().split())
  10.     pts.add(l)
  11.     pts.add(r)
  12.     if l in strt: strt[l].append(h)
  13.     else: strt[l] = [h]
  14.     if r in end: end[r].append(h)
  15.     else: end[r] = [h]
  16.    
  17. pts = sorted(list(pts))
  18.  
  19. mxh, hgt, hgt_d = 0, [(0, 0)], []
  20. for p in pts:
  21.     if p in strt:
  22.         for h in strt[p]:
  23.             heappush(hgt, (-h, h))
  24.     if p in end:
  25.         for h in end[p]:
  26.             heappush(hgt_d, (-h, h))
  27.    
  28.     tmp = []
  29.     while 1:
  30.         if not hgt_d : break
  31.         if hgt[0]!= hgt_d[0] : break
  32.         tmp.append(heappop(hgt))
  33.         heappop(hgt_d)
  34.        
  35.     n_mxh = hgt[0]
  36.    
  37.     for itm in tmp:
  38.         heappush(hgt, itm)
  39.         heappush(hgt_d, itm)
  40.    
  41.     if n_mxh != mxh:
  42.         sol.extend([p, n_mxh[1]])
  43.         mxh = n_mxh
  44.  
  45. print(' '.join(map(str, sol)))
Advertisement
Add Comment
Please, Sign In to add comment