Guest User

Untitled

a guest
Jun 28th, 2018
362
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.60 KB | None | 0 0
  1. import sys
  2. import bisect
  3.  
  4. lst = sys.stdin.readlines()
  5.    
  6. n = int(lst[0])
  7. a = [list(map(int, lst[i + 1].split())) for i in range(n)]
  8.  
  9. sh = []
  10. for i in range(n):
  11.     sh.append(a[i][0])
  12.     sh.append(a[i][1] + 1)
  13. sh.sort()
  14.  
  15. cnt = [0 for i in range(2 * n)]
  16. for i in range(n):
  17.     lpos = bisect.bisect_left(sh, a[i][0])
  18.     rpos = bisect.bisect_left(sh, a[i][1] + 1)
  19.     cnt[lpos] += 1
  20.     cnt[rpos] -= 1
  21. for i in range(1, 2 * n):
  22.     cnt[i] += cnt[i - 1]
  23.    
  24. ans = [0 for i in range(n + 1)]
  25. for i in range(1, 2 * n):
  26.     ans[cnt[i - 1]] += sh[i] - sh[i - 1]
  27.    
  28. sys.stdout.write(' '.join(str(x) for x in ans[1:n + 1]))
Advertisement
Add Comment
Please, Sign In to add comment