Submission #22152

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22152	2017-04-29T12:35:20 Z	xhae? xhae!(#1007, xhae)	None (KRIII5P_3)	PyPy	0 / 7	1000 ms	41 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 = [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

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	13 KB	Output is correct
2	Correct	81 ms	13 KB	Output is correct
3	Correct	87 ms	14 KB	Output is correct
4	Correct	88 ms	14 KB	Output is correct
5	Correct	90 ms	14 KB	Output is correct
6	Correct	246 ms	23 KB	Output is correct
7	Correct	230 ms	23 KB	Output is correct
8	Correct	237 ms	23 KB	Output is correct
9	Correct	241 ms	23 KB	Output is correct
10	Correct	234 ms	23 KB	Output is correct
11	Correct	788 ms	39 KB	Output is correct
12	Correct	823 ms	39 KB	Output is correct
13	Correct	791 ms	40 KB	Output is correct
14	Correct	845 ms	40 KB	Output is correct
15	Correct	852 ms	40 KB	Output is correct
16	Correct	836 ms	40 KB	Output is correct
17	Correct	841 ms	40 KB	Output is correct
18	Correct	890 ms	41 KB	Output is correct
19	Correct	832 ms	41 KB	Output is correct
20	Correct	793 ms	41 KB	Output is correct
21	Correct	981 ms	41 KB	Output is correct
22	Correct	973 ms	41 KB	Output is correct
23	Correct	998 ms	41 KB	Output is correct
24	Correct	972 ms	41 KB	Output is correct
25	Correct	863 ms	41 KB	Output is correct
26	Execution timed out	1040 ms	41 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-