Submission #22153

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22153	2017-04-29T12:37:44 Z	xhae? xhae!(#1007, xhae)	None (KRIII5P_3)	PyPy	0 / 7	1000 ms	43 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 = []
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	77 ms	13 KB	Output is correct
2	Correct	77 ms	13 KB	Output is correct
3	Correct	79 ms	14 KB	Output is correct
4	Correct	86 ms	14 KB	Output is correct
5	Correct	87 ms	14 KB	Output is correct
6	Correct	234 ms	22 KB	Output is correct
7	Correct	244 ms	24 KB	Output is correct
8	Correct	223 ms	24 KB	Output is correct
9	Correct	258 ms	24 KB	Output is correct
10	Correct	231 ms	24 KB	Output is correct
11	Correct	716 ms	42 KB	Output is correct
12	Correct	719 ms	42 KB	Output is correct
13	Correct	731 ms	42 KB	Output is correct
14	Correct	743 ms	42 KB	Output is correct
15	Correct	820 ms	42 KB	Output is correct
16	Correct	605 ms	42 KB	Output is correct
17	Correct	604 ms	42 KB	Output is correct
18	Correct	620 ms	42 KB	Output is correct
19	Correct	601 ms	42 KB	Output is correct
20	Correct	594 ms	42 KB	Output is correct
21	Correct	963 ms	43 KB	Output is correct
22	Correct	944 ms	43 KB	Output is correct
23	Correct	982 ms	43 KB	Output is correct
24	Correct	999 ms	43 KB	Output is correct
25	Correct	834 ms	43 KB	Output is correct
26	Execution timed out	1016 ms	43 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-