結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
ユーザー yupoohyupooh
提出日時 2024-02-23 21:58:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,232 ms / 2,500 ms
コード長 2,395 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 103,992 KB
最終ジャッジ日時 2024-02-23 22:00:03
合計ジャッジ時間 29,226 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,460 KB
testcase_01 AC 37 ms
53,460 KB
testcase_02 AC 506 ms
87,552 KB
testcase_03 AC 291 ms
80,100 KB
testcase_04 AC 831 ms
91,800 KB
testcase_05 AC 662 ms
88,924 KB
testcase_06 AC 435 ms
83,412 KB
testcase_07 AC 672 ms
88,972 KB
testcase_08 AC 415 ms
82,204 KB
testcase_09 AC 1,192 ms
103,604 KB
testcase_10 AC 1,216 ms
103,728 KB
testcase_11 AC 1,215 ms
103,992 KB
testcase_12 AC 1,178 ms
103,736 KB
testcase_13 AC 1,210 ms
103,604 KB
testcase_14 AC 1,185 ms
103,480 KB
testcase_15 AC 1,232 ms
103,476 KB
testcase_16 AC 909 ms
97,592 KB
testcase_17 AC 938 ms
97,412 KB
testcase_18 AC 910 ms
97,676 KB
testcase_19 AC 880 ms
97,684 KB
testcase_20 AC 894 ms
97,684 KB
testcase_21 AC 896 ms
97,692 KB
testcase_22 AC 921 ms
97,684 KB
testcase_23 AC 847 ms
97,684 KB
testcase_24 AC 847 ms
97,692 KB
testcase_25 AC 878 ms
97,584 KB
testcase_26 AC 860 ms
97,572 KB
testcase_27 AC 880 ms
97,700 KB
testcase_28 AC 825 ms
97,600 KB
testcase_29 AC 819 ms
97,600 KB
testcase_30 AC 593 ms
97,572 KB
testcase_31 AC 867 ms
97,700 KB
testcase_32 AC 627 ms
97,700 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