Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #1933
- import sys
- from heapq import *
- input = sys.stdin.readline
- pts, strt, end, sol = set(), {}, {}, []
- for _ in range(int(input())):
- l, h, r = map(int, input().split())
- pts.add(l)
- pts.add(r)
- if l in strt: strt[l].append(h)
- else: strt[l] = [h]
- if r in end: end[r].append(h)
- else: end[r] = [h]
- pts = sorted(list(pts))
- mxh, hgt, hgt_d = 0, [(0, 0)], []
- for p in pts:
- if p in strt:
- for h in strt[p]:
- heappush(hgt, (-h, h))
- if p in end:
- for h in end[p]:
- heappush(hgt_d, (-h, h))
- tmp = []
- while 1:
- if not hgt_d : break
- if hgt[0]!= hgt_d[0] : break
- tmp.append(heappop(hgt))
- heappop(hgt_d)
- n_mxh = hgt[0]
- for itm in tmp:
- heappush(hgt, itm)
- heappush(hgt_d, itm)
- if n_mxh != mxh:
- sol.extend([p, n_mxh[1]])
- mxh = n_mxh
- print(' '.join(map(str, sol)))
Advertisement
Add Comment
Please, Sign In to add comment