結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
ユーザー ニックネームニックネーム
提出日時 2024-02-23 21:46:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,236 ms / 2,500 ms
コード長 2,335 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 81,828 KB
実行使用メモリ 185,788 KB
最終ジャッジ日時 2024-02-23 21:46:54
合計ジャッジ時間 30,240 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,460 KB
testcase_01 AC 36 ms
53,460 KB
testcase_02 AC 398 ms
101,528 KB
testcase_03 AC 259 ms
91,136 KB
testcase_04 AC 873 ms
146,548 KB
testcase_05 AC 690 ms
123,028 KB
testcase_06 AC 394 ms
104,200 KB
testcase_07 AC 767 ms
135,856 KB
testcase_08 AC 328 ms
97,848 KB
testcase_09 AC 1,222 ms
184,920 KB
testcase_10 AC 1,227 ms
185,208 KB
testcase_11 AC 1,227 ms
185,064 KB
testcase_12 AC 1,220 ms
185,636 KB
testcase_13 AC 1,208 ms
185,788 KB
testcase_14 AC 1,236 ms
185,780 KB
testcase_15 AC 1,188 ms
185,288 KB
testcase_16 AC 970 ms
185,052 KB
testcase_17 AC 927 ms
184,992 KB
testcase_18 AC 959 ms
185,056 KB
testcase_19 AC 964 ms
185,652 KB
testcase_20 AC 946 ms
185,652 KB
testcase_21 AC 975 ms
185,660 KB
testcase_22 AC 988 ms
185,648 KB
testcase_23 AC 911 ms
184,444 KB
testcase_24 AC 880 ms
184,572 KB
testcase_25 AC 830 ms
184,592 KB
testcase_26 AC 862 ms
184,660 KB
testcase_27 AC 912 ms
184,720 KB
testcase_28 AC 936 ms
184,692 KB
testcase_29 AC 863 ms
184,532 KB
testcase_30 AC 820 ms
185,072 KB
testcase_31 AC 945 ms
184,784 KB
testcase_32 AC 453 ms
104,200 KB
権限があれば一括ダウンロードができます

ソースコード

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