제출 #551424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551424		jh05013	구간들 (KRIII5P_3)	Cpython 3	0 / 7	730 ms	42788 KiB

i

import sys;input=lambda:sys.stdin.readline().strip('\n')
MIS = lambda: map(int,input().split())
MOD = 10**9+7

pow2 = [1]
for i in range(100000): pow2.append(pow2[-1]*2 % MOD)

n = int(input())
ev_l = {}
ev_r = {}
for i in range(n):
    l, r = MIS()
    ev_l[l] = ev_l.get(l, 0) + 1
    ev_r[r] = ev_r.get(r, 0) + 1
pnts = sorted(set(list(ev_l.keys()) + list(ev_r.keys())))

ans0 = ans1 = 0
lay = 0
for i in range(len(pnts)-1):
    l, r = pnts[i], pnts[i+1]
    lay-= ev_r.get(l, 0)
    lay_old = lay
    lay+= ev_l.get(l, 0)
    ans0+= (pow2[lay]-1) * (r-l)
    ans1+= pow2[lay] - pow2[lay_old]
print(ans0%MOD, ans1%MOD)

• Subtask 1: 0 / 7