#784281 (PyPy3) No.1332 Range Nearest Query

• 問題: No.1332 Range Nearest Query
• ユーザー: titia
• 提出日時: 2022-08-04 01:39:40
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,755 ms / 2,500 ms
• コード長: 2,322 bytes
• コンパイル時間: 467 ms
• コンパイル使用メモリ: 82,272 KB
• 実行使用メモリ: 190,392 KB
• 最終ジャッジ日時: 2024-09-13 20:16:54
• 合計ジャッジ時間: 54,525 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
other	AC * 48

ソースコード

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import sys
input = sys.stdin.readline
from operator import itemgetter
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
Query=[tuple(map(int,input().split())) for i in range(Q)]
def seg_function(x,y): # Segment treeで扱うfunction
    return max(x,y)
seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[-1<<60]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
def update(n,x,seg_el): # A[n]をxへ更新
    i=n+seg_el
    SEG[i]=x
    i>>=1 # 子ノードへ
    
    while i!=0:
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=-1<<60
    while L<R:
        if L & 1:
            ANS=seg_function(ANS , SEG[L])
            L+=1
        if R & 1:
            R-=1
            ANS=seg_function(ANS , SEG[R])
        L>>=1
        R>>=1
    return ANS
ANS=[1<<60]*Q
QU=[]
for i in range(N):
    QU.append((A[i],i))
    
for i in range(Q):
    l,r,x=Query[i]
    QU.append((x,1<<60,l,r,i))
QU.sort(key=itemgetter(0))
for qu in QU:
    if len(qu)==2:
        ai,i=qu
        update(i,ai,seg_el)
    else:
        x,_,l,r,ind=qu
        vv=getvalues(l-1,r)
        ANS[ind]=min(ANS[ind],abs(vv-x))
seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[1<<60]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
def seg_function(x,y): # Segment treeで扱うfunction
    return min(x,y)
def update(n,x,seg_el): # A[n]をxへ更新
    i=n+seg_el
    SEG[i]=x
    i>>=1 # 子ノードへ
    
    while i!=0:
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=1<<60
    while L<R:
        if L & 1:
            ANS=seg_function(ANS , SEG[L])
            L+=1
        if R & 1:
            R-=1
            ANS=seg_function(ANS , SEG[R])
        L>>=1
        R>>=1
    return ANS
QU.sort(key=itemgetter(0),reverse=True)
for qu in QU:
    if len(qu)==2:
        ai,i=qu
        update(i,ai,seg_el)
    else:
        x,_,l,r,ind=qu
        vv=getvalues(l-1,r)
        ANS[ind]=min(ANS[ind],abs(vv-x))
print("\n".join(map(str,ANS)))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX