結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
ユーザー yupoohyupooh
提出日時 2024-02-23 21:58:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,249 ms / 2,500 ms
コード長 2,395 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 82,828 KB
実行使用メモリ 104,400 KB
最終ジャッジ日時 2024-09-29 06:35:28
合計ジャッジ時間 29,971 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,288 KB
testcase_01 AC 38 ms
53,384 KB
testcase_02 AC 482 ms
87,836 KB
testcase_03 AC 293 ms
80,316 KB
testcase_04 AC 778 ms
92,216 KB
testcase_05 AC 672 ms
89,864 KB
testcase_06 AC 417 ms
83,852 KB
testcase_07 AC 674 ms
88,928 KB
testcase_08 AC 372 ms
82,880 KB
testcase_09 AC 1,228 ms
103,768 KB
testcase_10 AC 1,225 ms
104,272 KB
testcase_11 AC 1,197 ms
104,280 KB
testcase_12 AC 1,198 ms
104,152 KB
testcase_13 AC 1,249 ms
104,032 KB
testcase_14 AC 1,231 ms
104,400 KB
testcase_15 AC 1,246 ms
103,896 KB
testcase_16 AC 942 ms
98,196 KB
testcase_17 AC 951 ms
97,940 KB
testcase_18 AC 965 ms
98,392 KB
testcase_19 AC 948 ms
97,864 KB
testcase_20 AC 938 ms
98,176 KB
testcase_21 AC 939 ms
97,956 KB
testcase_22 AC 955 ms
97,908 KB
testcase_23 AC 864 ms
98,332 KB
testcase_24 AC 878 ms
98,340 KB
testcase_25 AC 871 ms
97,892 KB
testcase_26 AC 896 ms
98,352 KB
testcase_27 AC 908 ms
98,180 KB
testcase_28 AC 869 ms
98,088 KB
testcase_29 AC 855 ms
98,392 KB
testcase_30 AC 614 ms
97,960 KB
testcase_31 AC 912 ms
98,196 KB
testcase_32 AC 639 ms
98,000 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
n,a=map(int,input().split())
x=list(map(int,input().split()))
class LazySegTree:
 
    def __init__(self, N, func, intv):
        self.intv = intv
        self.func = func
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [intv]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)
 
    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        v = 2
        for i in range(self.LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1; v <<= 1
 
    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v >> 1
            self.lazy[i-1] = None
 
    def update(self, l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        L = self.N0 + l; R = self.N0 + r
        v = x
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = v
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = v
                L += 1
            L >>= 1; R >>= 1; v <<= 1
        for i in ids:
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i])
 
    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
 
def segfunc(x, y):
    return x + y
xx=[]
for i in range(n):
  xx.append((x[i],i))
xx.sort()
x.sort()
inv=[0]*n
for i in range(n):
  inv[xx[i][1]]=i
st=LazySegTree(n,segfunc,0)
t=int(input())
from bisect import bisect_left, bisect_right, insort
for i in range(t):
  l,r=map(int,input().split())
  id1=bisect_left(x,l)
  if id1==n:
    continue
  id2=bisect_right(x,r)-1
  st.update(id1,id2+1,i+1)
for i in range(n):
  ans=st.query(inv[i],inv[i]+1)
  if ans==0:
    print(-1)
  else:
    print(ans)
0