Submission #22149

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22149	2017-04-29T12:31:03 Z	xhae? xhae!(#1007, xhae)	None (KRIII5P_3)	PyPy	7 / 7	996 ms	42 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 = []
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

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	14 KB	Output is correct
2	Correct	79 ms	14 KB	Output is correct
3	Correct	83 ms	14 KB	Output is correct
4	Correct	89 ms	14 KB	Output is correct
5	Correct	88 ms	14 KB	Output is correct
6	Correct	237 ms	22 KB	Output is correct
7	Correct	216 ms	23 KB	Output is correct
8	Correct	212 ms	23 KB	Output is correct
9	Correct	225 ms	23 KB	Output is correct
10	Correct	221 ms	23 KB	Output is correct
11	Correct	743 ms	40 KB	Output is correct
12	Correct	771 ms	40 KB	Output is correct
13	Correct	755 ms	41 KB	Output is correct
14	Correct	760 ms	41 KB	Output is correct
15	Correct	756 ms	41 KB	Output is correct
16	Correct	589 ms	41 KB	Output is correct
17	Correct	571 ms	41 KB	Output is correct
18	Correct	516 ms	41 KB	Output is correct
19	Correct	534 ms	41 KB	Output is correct
20	Correct	521 ms	41 KB	Output is correct
21	Correct	946 ms	41 KB	Output is correct
22	Correct	941 ms	41 KB	Output is correct
23	Correct	916 ms	41 KB	Output is correct
24	Correct	888 ms	41 KB	Output is correct
25	Correct	851 ms	41 KB	Output is correct
26	Correct	927 ms	41 KB	Output is correct
27	Correct	996 ms	41 KB	Output is correct
28	Correct	941 ms	41 KB	Output is correct
29	Correct	938 ms	41 KB	Output is correct
30	Correct	896 ms	41 KB	Output is correct
31	Correct	911 ms	41 KB	Output is correct
32	Correct	889 ms	41 KB	Output is correct
33	Correct	760 ms	41 KB	Output is correct
34	Correct	904 ms	41 KB	Output is correct
35	Correct	854 ms	41 KB	Output is correct
36	Correct	965 ms	41 KB	Output is correct
37	Correct	912 ms	41 KB	Output is correct
38	Correct	930 ms	42 KB	Output is correct
39	Correct	838 ms	42 KB	Output is correct
40	Correct	919 ms	42 KB	Output is correct
41	Correct	113 ms	42 KB	Output is correct
42	Correct	92 ms	42 KB	Output is correct
43	Correct	206 ms	42 KB	Output is correct
44	Correct	198 ms	42 KB	Output is correct
45	Correct	473 ms	42 KB	Output is correct
46	Correct	316 ms	42 KB	Output is correct
47	Correct	376 ms	42 KB	Output is correct
48	Correct	767 ms	42 KB	Output is correct
49	Correct	599 ms	42 KB	Output is correct
50	Correct	676 ms	42 KB	Output is correct