제출 #551426

#제출 시각아이디문제언어결과실행 시간메모리
551426jh05013구간들 (KRIII5P_3)Cpython 3
7 / 7
704 ms42868 KiB
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(100003): pow2.append(pow2[-1]*2 % MOD)

n = int(input())
ev_l = {}
ev_r = {}
for i in range(n):
    l, r = MIS()
    if l >= r: continue
    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)
#Verdict Execution timeMemoryGrader output
Fetching results...