Submission #551426

#	Time	Username	Problem	Language	Result	Execution time	Memory
551426		jh05013	구간들 (KRIII5P_3)	Cpython 3	7 / 7	704 ms	42868 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(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)

• Subtask 1: 7 / 7