Submission #22155

# Submission time Handle Problem Language Result Execution time Memory
22155 2017-04-29T12:48:41 Z xhae? xhae!(#1007, xhae) None (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 = sorted(data[:di])

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 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 87 ms 14 KB Output is correct
5 Correct 84 ms 14 KB Output is correct
6 Correct 232 ms 23 KB Output is correct
7 Correct 228 ms 23 KB Output is correct
8 Correct 239 ms 23 KB Output is correct
9 Correct 227 ms 23 KB Output is correct
10 Correct 294 ms 23 KB Output is correct
11 Correct 742 ms 40 KB Output is correct
12 Correct 791 ms 40 KB Output is correct
13 Correct 781 ms 41 KB Output is correct
14 Correct 806 ms 41 KB Output is correct
15 Correct 768 ms 41 KB Output is correct
16 Correct 600 ms 41 KB Output is correct
17 Correct 604 ms 41 KB Output is correct
18 Correct 595 ms 41 KB Output is correct
19 Correct 619 ms 41 KB Output is correct
20 Correct 570 ms 41 KB Output is correct
21 Correct 936 ms 41 KB Output is correct
22 Correct 979 ms 41 KB Output is correct
23 Execution timed out 1004 ms 41 KB Time limit exceeded
24 Halted 0 ms 0 KB -