#954329 (PyPy3) No.2650 [Cherry 6th Tune *] セイジャク

• 問題: No.2650 [Cherry 6th Tune *] セイジャク
• ユーザー: yupooh
• 提出日時: 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

ファイルパターン	結果
sample	AC * 2
other	AC * 31

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX