| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 22149 | 2017-04-29T12:31:03 Z | xhae? xhae!(#1007, xhae) | 구간들 (KRIII5P_3) | PyPy | 996 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 | 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 | 89 ms | 14 KB | Output is correct |
| 5 | Correct | 88 ms | 14 KB | Output is correct |
| 6 | Correct | 237 ms | 22 KB | Output is correct |
| 7 | Correct | 216 ms | 23 KB | Output is correct |
| 8 | Correct | 212 ms | 23 KB | Output is correct |
| 9 | Correct | 225 ms | 23 KB | Output is correct |
| 10 | Correct | 221 ms | 23 KB | Output is correct |
| 11 | Correct | 743 ms | 40 KB | Output is correct |
| 12 | Correct | 771 ms | 40 KB | Output is correct |
| 13 | Correct | 755 ms | 41 KB | Output is correct |
| 14 | Correct | 760 ms | 41 KB | Output is correct |
| 15 | Correct | 756 ms | 41 KB | Output is correct |
| 16 | Correct | 589 ms | 41 KB | Output is correct |
| 17 | Correct | 571 ms | 41 KB | Output is correct |
| 18 | Correct | 516 ms | 41 KB | Output is correct |
| 19 | Correct | 534 ms | 41 KB | Output is correct |
| 20 | Correct | 521 ms | 41 KB | Output is correct |
| 21 | Correct | 946 ms | 41 KB | Output is correct |
| 22 | Correct | 941 ms | 41 KB | Output is correct |
| 23 | Correct | 916 ms | 41 KB | Output is correct |
| 24 | Correct | 888 ms | 41 KB | Output is correct |
| 25 | Correct | 851 ms | 41 KB | Output is correct |
| 26 | Correct | 927 ms | 41 KB | Output is correct |
| 27 | Correct | 996 ms | 41 KB | Output is correct |
| 28 | Correct | 941 ms | 41 KB | Output is correct |
| 29 | Correct | 938 ms | 41 KB | Output is correct |
| 30 | Correct | 896 ms | 41 KB | Output is correct |
| 31 | Correct | 911 ms | 41 KB | Output is correct |
| 32 | Correct | 889 ms | 41 KB | Output is correct |
| 33 | Correct | 760 ms | 41 KB | Output is correct |
| 34 | Correct | 904 ms | 41 KB | Output is correct |
| 35 | Correct | 854 ms | 41 KB | Output is correct |
| 36 | Correct | 965 ms | 41 KB | Output is correct |
| 37 | Correct | 912 ms | 41 KB | Output is correct |
| 38 | Correct | 930 ms | 42 KB | Output is correct |
| 39 | Correct | 838 ms | 42 KB | Output is correct |
| 40 | Correct | 919 ms | 42 KB | Output is correct |
| 41 | Correct | 113 ms | 42 KB | Output is correct |
| 42 | Correct | 92 ms | 42 KB | Output is correct |
| 43 | Correct | 206 ms | 42 KB | Output is correct |
| 44 | Correct | 198 ms | 42 KB | Output is correct |
| 45 | Correct | 473 ms | 42 KB | Output is correct |
| 46 | Correct | 316 ms | 42 KB | Output is correct |
| 47 | Correct | 376 ms | 42 KB | Output is correct |
| 48 | Correct | 767 ms | 42 KB | Output is correct |
| 49 | Correct | 599 ms | 42 KB | Output is correct |
| 50 | Correct | 676 ms | 42 KB | Output is correct |