답안 #22157

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22157 2017-04-29T12:50:57 Z xhae? xhae!(#1007, xhae) 구간들 (KRIII5P_3) PyPy
0 / 7
1000 ms 41 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(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 = [0] * (len(data) * 2)
for i in range(len(data)):
	coords[i * 2] = data[i][0]
	coords[i * 2 + 1] = data[i][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 94 ms 14 KB Output is correct
2 Correct 82 ms 14 KB Output is correct
3 Correct 95 ms 14 KB Output is correct
4 Correct 98 ms 14 KB Output is correct
5 Correct 86 ms 14 KB Output is correct
6 Correct 230 ms 22 KB Output is correct
7 Correct 209 ms 23 KB Output is correct
8 Correct 222 ms 23 KB Output is correct
9 Correct 221 ms 23 KB Output is correct
10 Correct 238 ms 23 KB Output is correct
11 Correct 755 ms 40 KB Output is correct
12 Correct 703 ms 41 KB Output is correct
13 Correct 735 ms 41 KB Output is correct
14 Correct 757 ms 41 KB Output is correct
15 Correct 787 ms 41 KB Output is correct
16 Correct 586 ms 41 KB Output is correct
17 Correct 575 ms 41 KB Output is correct
18 Correct 562 ms 41 KB Output is correct
19 Correct 558 ms 41 KB Output is correct
20 Correct 539 ms 41 KB Output is correct
21 Correct 949 ms 41 KB Output is correct
22 Correct 934 ms 41 KB Output is correct
23 Correct 920 ms 41 KB Output is correct
24 Execution timed out 1018 ms 41 KB Time limit exceeded
25 Halted 0 ms 0 KB -