답안 #22143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22143 2017-04-29T12:06:06 Z xhae? xhae!(#1007, xhae) 구간들 (KRIII5P_3) Python 3
0 / 7
1000 ms 32 KB
# 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(input())
_data = sorted([tuple(map(int, input().split())) for i in range(n)])
data = []
for cpair in _data:
	if cpair[0] >= cpair[1]:
		continue
	data += [cpair]

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)
# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 14 KB Output is correct
2 Correct 92 ms 14 KB Output is correct
3 Correct 95 ms 14 KB Output is correct
4 Correct 95 ms 14 KB Output is correct
5 Correct 88 ms 14 KB Output is correct
6 Correct 174 ms 16 KB Output is correct
7 Correct 175 ms 16 KB Output is correct
8 Correct 173 ms 16 KB Output is correct
9 Correct 175 ms 16 KB Output is correct
10 Correct 173 ms 16 KB Output is correct
11 Execution timed out 1071 ms 32 KB Time limit exceeded
12 Halted 0 ms 0 KB -