結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー | ゼット |
提出日時 | 2024-02-23 22:09:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 901 ms / 2,500 ms |
コード長 | 1,801 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 126,912 KB |
最終ジャッジ日時 | 2024-02-23 22:09:37 |
合計ジャッジ時間 | 25,051 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
53,460 KB |
testcase_01 | AC | 35 ms
53,460 KB |
testcase_02 | AC | 393 ms
105,604 KB |
testcase_03 | AC | 345 ms
80,996 KB |
testcase_04 | AC | 668 ms
90,468 KB |
testcase_05 | AC | 576 ms
90,236 KB |
testcase_06 | AC | 404 ms
82,588 KB |
testcase_07 | AC | 574 ms
87,304 KB |
testcase_08 | AC | 411 ms
83,176 KB |
testcase_09 | AC | 895 ms
126,560 KB |
testcase_10 | AC | 861 ms
126,728 KB |
testcase_11 | AC | 860 ms
126,680 KB |
testcase_12 | AC | 901 ms
126,680 KB |
testcase_13 | AC | 796 ms
126,716 KB |
testcase_14 | AC | 814 ms
126,716 KB |
testcase_15 | AC | 814 ms
126,840 KB |
testcase_16 | AC | 838 ms
126,668 KB |
testcase_17 | AC | 886 ms
126,440 KB |
testcase_18 | AC | 843 ms
126,888 KB |
testcase_19 | AC | 837 ms
126,704 KB |
testcase_20 | AC | 879 ms
126,704 KB |
testcase_21 | AC | 871 ms
126,912 KB |
testcase_22 | AC | 901 ms
126,704 KB |
testcase_23 | AC | 745 ms
126,704 KB |
testcase_24 | AC | 716 ms
126,716 KB |
testcase_25 | AC | 788 ms
126,656 KB |
testcase_26 | AC | 733 ms
126,728 KB |
testcase_27 | AC | 710 ms
126,724 KB |
testcase_28 | AC | 766 ms
126,876 KB |
testcase_29 | AC | 732 ms
126,680 KB |
testcase_30 | AC | 621 ms
126,152 KB |
testcase_31 | AC | 607 ms
126,728 KB |
testcase_32 | AC | 404 ms
126,728 KB |
ソースコード
class segtree: def __init__(self,n): self.size=1 self.height=0 while self.size<n: self.size*=2 self.height+=1 self.dat=[-1]*(self.size*2) self.lazy=[-1]*(self.size*2) def lazyup(self,l,r,a): l+=self.size r+=self.size while l<r: if l&1: self.lazy[l]=max(self.lazy[l],a) l+=1 if r&1: r-=1 self.lazy[r]=max(self.lazy[r],a) l//=2 r//=2 def querry(self,l,r): l+=self.size r+=self.size score=-10**20 while l<r: if l&1: w=max(self.dat[l],self.lazy[l]) score=max(score,w) l+=1 if r&1: r-=1 w=max(self.dat[r],self.lazy[r]) score=max(score,w) l//=2 r//=2 return score def propagate(self,x): x+=self.size for h in range(self.height,0,-1): y=x>>h self.lazy[2*y]=max(self.lazy[y],self.lazy[2*y]) self.lazy[2*y+1]=max(self.lazy[y],self.lazy[2*y+1]) self.dat[y]=max(self.dat[y],self.lazy[y]) self.lazy[y]=-1 def bottom(self,x): x+=self.size while x>1: x//=2 self.dat[x]=max(max(self.dat[2*x],self.lazy[2*x]),max(self.dat[2*x+1],self.lazy[2*x+1])) N,ppp=map(int,input().split()) A=list(map(int,input().split())) B=set() for i in range(N): B.add(A[i]) B=list(B) B.sort() T={} for i in range(len(B)): T[B[i]]=i M=len(B) Z=segtree(M) K=int(input()) from bisect import bisect_left,bisect_right for t in range(1,K+1): l,r=map(int,input().split()) pos1=bisect_left(B,l) pos2=bisect_right(B,r) Z.propagate(pos1) Z.propagate(pos2-1) Z.lazyup(pos1,pos2,t) Z.bottom(pos1) Z.bottom(pos2-1) for i in range(N): pos=T[A[i]] Z.propagate(pos) ans=Z.querry(pos,pos+1) print(ans)