Submission #22158

# Submission time Handle Problem Language Result Execution time Memory
22158 2017-04-29T12:52:48 Z xhae? xhae!(#1007, xhae) None (KRIII5P_3) PyPy
7 / 7
989 ms 42 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
# Verdict Execution time Memory Grader output
1 Correct 79 ms 14 KB Output is correct
2 Correct 77 ms 14 KB Output is correct
3 Correct 83 ms 14 KB Output is correct
4 Correct 90 ms 14 KB Output is correct
5 Correct 88 ms 14 KB Output is correct
6 Correct 250 ms 22 KB Output is correct
7 Correct 222 ms 23 KB Output is correct
8 Correct 234 ms 23 KB Output is correct
9 Correct 231 ms 23 KB Output is correct
10 Correct 222 ms 23 KB Output is correct
11 Correct 702 ms 40 KB Output is correct
12 Correct 722 ms 41 KB Output is correct
13 Correct 760 ms 41 KB Output is correct
14 Correct 772 ms 41 KB Output is correct
15 Correct 756 ms 41 KB Output is correct
16 Correct 581 ms 41 KB Output is correct
17 Correct 563 ms 41 KB Output is correct
18 Correct 547 ms 41 KB Output is correct
19 Correct 585 ms 41 KB Output is correct
20 Correct 563 ms 41 KB Output is correct
21 Correct 938 ms 41 KB Output is correct
22 Correct 913 ms 41 KB Output is correct
23 Correct 906 ms 41 KB Output is correct
24 Correct 859 ms 41 KB Output is correct
25 Correct 826 ms 41 KB Output is correct
26 Correct 925 ms 41 KB Output is correct
27 Correct 922 ms 41 KB Output is correct
28 Correct 908 ms 41 KB Output is correct
29 Correct 898 ms 41 KB Output is correct
30 Correct 927 ms 41 KB Output is correct
31 Correct 989 ms 41 KB Output is correct
32 Correct 894 ms 41 KB Output is correct
33 Correct 872 ms 41 KB Output is correct
34 Correct 746 ms 41 KB Output is correct
35 Correct 813 ms 41 KB Output is correct
36 Correct 960 ms 41 KB Output is correct
37 Correct 882 ms 41 KB Output is correct
38 Correct 949 ms 42 KB Output is correct
39 Correct 832 ms 42 KB Output is correct
40 Correct 901 ms 42 KB Output is correct
41 Correct 115 ms 42 KB Output is correct
42 Correct 91 ms 42 KB Output is correct
43 Correct 231 ms 42 KB Output is correct
44 Correct 216 ms 42 KB Output is correct
45 Correct 476 ms 42 KB Output is correct
46 Correct 315 ms 42 KB Output is correct
47 Correct 364 ms 42 KB Output is correct
48 Correct 830 ms 42 KB Output is correct
49 Correct 620 ms 42 KB Output is correct
50 Correct 642 ms 42 KB Output is correct