답안 #22143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22143	2017-04-29T12:06:06 Z	xhae? xhae!(#1007, xhae)	구간들 (KRIII5P_3)	Python 3	0 / 7	1000 ms	32 KB

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(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)

Subtask #1

0 / 7.0

#	결과	실행 시간	메모리	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	-