답안 #22156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22156 2017-04-29T12:49:39 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 = [0] * n
di = 0
for i in range(n):
	cpair = tuple(map(int, raw_input().split()))
	if cpair[0] >= cpair[1]:
		continue
	data[di] = cpair
	di += 1
data = data[:di]
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 79 ms 14 KB Output is correct
2 Correct 79 ms 14 KB Output is correct
3 Correct 86 ms 14 KB Output is correct
4 Correct 89 ms 14 KB Output is correct
5 Correct 84 ms 14 KB Output is correct
6 Correct 222 ms 23 KB Output is correct
7 Correct 220 ms 23 KB Output is correct
8 Correct 218 ms 23 KB Output is correct
9 Correct 229 ms 24 KB Output is correct
10 Correct 227 ms 24 KB Output is correct
11 Correct 728 ms 40 KB Output is correct
12 Correct 744 ms 40 KB Output is correct
13 Correct 761 ms 41 KB Output is correct
14 Correct 771 ms 41 KB Output is correct
15 Correct 807 ms 41 KB Output is correct
16 Correct 610 ms 41 KB Output is correct
17 Correct 592 ms 41 KB Output is correct
18 Correct 598 ms 41 KB Output is correct
19 Correct 612 ms 41 KB Output is correct
20 Correct 570 ms 41 KB Output is correct
21 Correct 960 ms 41 KB Output is correct
22 Correct 969 ms 41 KB Output is correct
23 Execution timed out 1018 ms 41 KB Time limit exceeded
24 Halted 0 ms 0 KB -