Submission #22153

#	Time	Username	Problem	Language	Result	Execution time	Memory
22153		xhae? xhae! (#42)	구간들 (KRIII5P_3)	Pypy 2	0 / 7	1016 ms	43 KiB

i

# date:		2017-04-29
# contest:	5th kriiicon
# problem:	I
# author:	xhae

import itertools
import heapq

MOD = 1000000007
pows = [1] * 1000001
for i in range(1, 100001):
	pows[i] = pows[i - 1] * 2 % MOD

n = int(raw_input())
data = []
for i in range(n):
        cpair = tuple(map(int, raw_input().split()))
        if cpair[0] >= cpair[1]:
                continue
        data += [cpair]
data = sorted(data)

coords = []
for coord in data:
	coords += [coord[0]]
	coords += [coord[1]]
coords = [k for k, g in itertools.groupby(sorted(coords))]

# sub problem 1
endQueue = []
di = 0
totLen = 0
for i in range(len(coords) - 1):
	while di < len(data):
		if data[di][0] <= coords[i]:
			heapq.heappush(endQueue, data[di][1])
			di += 1
		else:
			break
	
	while len(endQueue) > 0 and endQueue[0] <= coords[i]:
		heapq.heappop(endQueue)

	curLen = coords[i + 1] - coords[i]
	totLen = (totLen + curLen * (pows[len(endQueue)] - 1)) % MOD

# sub problem 2
nCases = 0
endQueue = []
for coord in data:
	while len(endQueue) > 0 and endQueue[0] <= coord[0]:
		heapq.heappop(endQueue)
	nCases = (nCases + pows[len(endQueue)]) % MOD
	heapq.heappush(endQueue, coord[1])

print totLen, nCases

• Subtask 1: 0 / 7