結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
ユーザー ニックネームニックネーム
提出日時 2024-02-23 21:46:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,273 ms / 2,500 ms
コード長 2,335 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 186,360 KB
最終ジャッジ日時 2024-09-29 06:07:19
合計ジャッジ時間 30,995 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LazySegmentTreeUpdate:
    def segfunc(self,x,y):
        return min(x,y)
    def __init__(self,first_list,first_value):
        n = len(first_list)
        self.first_value = first_value
        self.num = 1<<(n-1).bit_length()
        self.data = [first_value]*2*self.num
        self.lazy = [None]*2*self.num
        for i in range(n):
            self.data[self.num+i] = first_list[i]
        for i in range(self.num-1,0,-1):
            self.data[i] = self.segfunc(self.data[2*i],self.data[2*i+1])
    def gindex(self,l,r):
        l += self.num; lm = l>>(l&-l).bit_length()
        r += self.num; rm = r>>(r&-r).bit_length()
        while l<r:
            if r<=rm: yield r
            if l<=lm: yield l
            l >>= 1; r >>= 1
        while l:
            yield l
            l >>= 1
    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2*i] = v; self.lazy[2*i+1] = v
            self.data[2*i] = v; self.data[2*i+1] = v
            self.lazy[i] = None
    def update(self,l,r,x):
        *ids,= self.gindex(l,r)
        self.propagates(*ids)
        l += self.num; r += self.num
        while l<r:
            if l&1:
                self.lazy[l] = x; self.data[l] = x
                l += 1
            if r&1:
                self.lazy[r-1] = x; self.data[r-1] = x
            l >>= 1; r >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2*i],self.data[2*i+1])
    def query(self,l,r):
        *ids,= self.gindex(l,r)
        self.propagates(*ids)
        res = self.first_value
        l += self.num; r += self.num
        while l<r:
            if l&1:
                res = self.segfunc(res,self.data[l])
                l += 1
            if r&1:
                res = self.segfunc(res,self.data[r-1])
            l >>= 1; r >>= 1
        return res
n,a = map(int,input().split())
x = list(map(int,input().split()))
s = set(x); t = int(input()); lr = []
for _ in range(t):
    l,r = map(int,input().split())
    s |= {l,r+1}; lr.append((l,r+1))
d = {v:i for i,v in enumerate(sorted(s))}
lst = LazySegmentTreeUpdate([10**6]*len(d),10**6)
for i in range(t): lst.update(d[lr[i][0]],d[lr[i][1]],i+1)
for v in x:
    i = lst.query(d[v],d[v]+1)
    print(i if i<10**6 else -1)
0