結果

問題 No.2220 Range Insert & Point Mex
ユーザー roarisroaris
提出日時 2023-02-18 02:02:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,200 bytes
コンパイル時間 1,460 ms
コンパイル使用メモリ 86,944 KB
実行使用メモリ 260,728 KB
最終ジャッジ日時 2023-09-26 22:43:16
合計ジャッジ時間 11,965 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
78,580 KB
testcase_01 AC 89 ms
71,604 KB
testcase_02 AC 91 ms
71,492 KB
testcase_03 WA -
testcase_04 AC 89 ms
71,396 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 95 ms
77,068 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 TLE -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from collections import *

def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)

    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N = int(input())
lra = [tuple(map(int, input().split())) for _ in range(N)]
Q = int(input())
x = list(map(int, input().split()))
idx = compress(x+[l for l, _, _ in lra]+[r for _, r, _ in lra])
d1 = defaultdict(list)

for l, r, a in lra:
    d1[a].append((idx[l], idx[r]))

d2 = defaultdict(list)

for a in d1.keys():
    now_l, now_r = d1[a][0]
    
    for l, r in d1[a][1:]:
        if l<=now_r:
            now_r = max(now_r, r)
        else:
            d2[a].append((now_l, now_r))
            now_l, now_r = l, r
    
    d2[a].append((now_l, now_r))

al = list(sorted(d2.keys()))
ok = [-1]*Q
ng = [10**9+10]*Q

while True:
    finish = True
    mid_idx = defaultdict(list)
    
    for i in range(Q):
        if abs(ok[i]-ng[i])>1:
            finish = False
            mid = (ok[i]+ng[i])//2
            mid_idx[mid].append(i)
    
    if finish:
        break
    
    mids = list(sorted(mid_idx.keys(), reverse=True))
    bit = BIT(len(idx.keys()))
    
    for a in al:
        while len(mids) and a>mids[-1]:
            mid = mids.pop()
            
            for i in mid_idx[mid]:
                ng[i] = mid

        for l, r in d2[a]:
            bit.add(l, 1)
            bit.add(r+1, -1)
        
        if len(mids) and a==mids[-1]:
            mid = mids.pop()
            
            for i in mid_idx[mid]:
                if bit.acc(idx[x[i]]+1)==a+1:
                    ok[i] = mid
                else:
                    ng[i] = mid
    
    while mids:
        mid = mids.pop()
            
        for i in mid_idx[mid]:
            ng[i] = mid

for i in range(Q):
    print(ok[i]+1)
0