| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 22158 | 2017-04-29T12:52:48 Z | xhae? xhae!(#1007, xhae) | 구간들 (KRIII5P_3) | PyPy | 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
| # | 결과 | 실행 시간 | 메모리 | 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 |