結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
ユーザー yupoohyupooh
提出日時 2024-02-23 21:57:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,386 bytes
コンパイル時間 621 ms
コンパイル使用メモリ 81,976 KB
実行使用メモリ 98,588 KB
最終ジャッジ日時 2024-09-29 06:31:36
合計ジャッジ時間 25,962 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,484 KB
testcase_01 AC 40 ms
53,336 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
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 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 645 ms
97,920 KB
testcase_31 WA -
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

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()
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