結果

問題 No.2220 Range Insert & Point Mex
コンテスト
ユーザー roaris
提出日時 2023-02-18 02:02:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,200 bytes
コンパイル時間 785 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 259,708 KB
最終ジャッジ日時 2024-07-19 16:28:12
合計ジャッジ時間 11,559 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 15 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

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