結果
問題 | No.2220 Range Insert & Point Mex |
ユーザー | ああいい |
提出日時 | 2023-02-18 18:36:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,001 ms / 2,000 ms |
コード長 | 1,902 bytes |
コンパイル時間 | 835 ms |
コンパイル使用メモリ | 86,980 KB |
実行使用メモリ | 112,820 KB |
最終ジャッジ日時 | 2023-09-28 18:21:30 |
合計ジャッジ時間 | 22,402 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 96 ms
72,468 KB |
testcase_01 | AC | 95 ms
72,740 KB |
testcase_02 | AC | 97 ms
72,444 KB |
testcase_03 | AC | 103 ms
77,824 KB |
testcase_04 | AC | 96 ms
72,344 KB |
testcase_05 | AC | 104 ms
77,476 KB |
testcase_06 | AC | 105 ms
77,520 KB |
testcase_07 | AC | 106 ms
77,600 KB |
testcase_08 | AC | 102 ms
77,500 KB |
testcase_09 | AC | 103 ms
77,676 KB |
testcase_10 | AC | 102 ms
77,560 KB |
testcase_11 | AC | 103 ms
77,020 KB |
testcase_12 | AC | 105 ms
77,476 KB |
testcase_13 | AC | 990 ms
104,368 KB |
testcase_14 | AC | 971 ms
104,384 KB |
testcase_15 | AC | 977 ms
104,520 KB |
testcase_16 | AC | 983 ms
104,200 KB |
testcase_17 | AC | 1,001 ms
104,568 KB |
testcase_18 | AC | 969 ms
104,012 KB |
testcase_19 | AC | 973 ms
104,216 KB |
testcase_20 | AC | 741 ms
106,436 KB |
testcase_21 | AC | 761 ms
106,160 KB |
testcase_22 | AC | 752 ms
106,880 KB |
testcase_23 | AC | 674 ms
112,820 KB |
testcase_24 | AC | 543 ms
109,852 KB |
testcase_25 | AC | 546 ms
98,504 KB |
testcase_26 | AC | 618 ms
102,784 KB |
testcase_27 | AC | 389 ms
98,788 KB |
testcase_28 | AC | 320 ms
91,508 KB |
testcase_29 | AC | 142 ms
93,852 KB |
testcase_30 | AC | 141 ms
93,844 KB |
testcase_31 | AC | 535 ms
104,088 KB |
testcase_32 | AC | 376 ms
99,060 KB |
testcase_33 | AC | 447 ms
98,948 KB |
testcase_34 | AC | 825 ms
104,416 KB |
testcase_35 | AC | 891 ms
103,956 KB |
testcase_36 | AC | 841 ms
102,536 KB |
testcase_37 | AC | 921 ms
103,244 KB |
testcase_38 | AC | 470 ms
102,512 KB |
ソースコード
#BIT plus ver class BITplus: def __init__(self,N): self.N = N self.bit = [0] * (self.N+1) def add(self,i,x): while i <= self.N: self.bit[i] += x i += i & -i def fold(self,i): ans = 0 while i > 0: ans += self.bit[i] i -= i & -i return ans def lb(self,w): if w <= 0:return 0 x = 0 k = 1 while k <= self.N: k <<= 1 k >>= 1 while k: if x + k <= self.N and self.bit[x+k] < w: w -= self.bit[x+k] x += k k >>= 1 return x + 1 #サイズ N の配列をいれる """ def build(self,seq): bit = self.bit N = self.N for i in range(N): bit[i+1] = seq[i] for i in range(1,N+1): if i + (i & -1) <= N: bit[i + (i & -i)] += bit[i] """ N = int(input()) query = [] for _ in range(N): l,r,a = map(int,input().split()) query.append((l,a)) query.append((r + 1,~a)) query.sort(reverse = True) Q = int(input()) X = list(map(int,input().split())) C = 10 ** 5 bit = BITplus(C + 1) from collections import defaultdict d = defaultdict(int) def calc(): if 0 not in d or d[0] == 0: return 0 end = C + 1 start = 0 while end - start > 1: mid = end + start >> 1 u = bit.fold(mid + 1) if u <= mid: end = mid else: start = mid return start + 1 for x in X: while query and query[-1][0] <= x: k,a = query.pop() if a < 0: a = ~a if a > C:continue d[a] -= 1 if d[a] == 0: bit.add(a + 1,-1) else: if a > C:continue d[a] += 1 if d[a] == 1: bit.add(a + 1,1) print(calc())