Submission #22145

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22145	2017-04-29T12:15:00 Z	xhae? xhae!(#1007, xhae)	None (KRIII5P_3)	PyPy	0 / 7	1000 ms	44 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(raw_input())
_data = sorted([tuple(map(int, raw_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

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	14 KB	Output is correct
2	Correct	91 ms	14 KB	Output is correct
3	Correct	78 ms	14 KB	Output is correct
4	Correct	77 ms	14 KB	Output is correct
5	Correct	91 ms	14 KB	Output is correct
6	Correct	203 ms	22 KB	Output is correct
7	Correct	247 ms	23 KB	Output is correct
8	Correct	211 ms	23 KB	Output is correct
9	Correct	230 ms	23 KB	Output is correct
10	Correct	232 ms	23 KB	Output is correct
11	Correct	744 ms	40 KB	Output is correct
12	Correct	719 ms	40 KB	Output is correct
13	Correct	705 ms	40 KB	Output is correct
14	Correct	805 ms	40 KB	Output is correct
15	Correct	783 ms	40 KB	Output is correct
16	Correct	818 ms	40 KB	Output is correct
17	Correct	854 ms	40 KB	Output is correct
18	Correct	938 ms	40 KB	Output is correct
19	Correct	883 ms	41 KB	Output is correct
20	Correct	755 ms	41 KB	Output is correct
21	Correct	939 ms	44 KB	Output is correct
22	Correct	939 ms	44 KB	Output is correct
23	Execution timed out	1034 ms	44 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-