結果
問題 |
No.3238 Shadow
|
ユーザー |
![]() |
提出日時 | 2025-08-15 22:21:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 313 ms / 2,000 ms |
コード長 | 1,096 bytes |
コンパイル時間 | 321 ms |
コンパイル使用メモリ | 82,772 KB |
実行使用メモリ | 120,944 KB |
最終ジャッジ日時 | 2025-08-15 22:21:06 |
合計ジャッジ時間 | 4,598 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
class segtree: def __init__(self,n): self.size=1 while self.size<n: self.size*=2 self.dat=[-1]*(self.size*2) def update(self,x,a): x+=self.size self.dat[x]=a while x>1: x//=2 self.dat[x]=max(self.dat[2*x],self.dat[2*x+1]) def querry(self,u,v): u+=self.size v+=self.size score=-1 while u<v: if u&1: score=max(score,self.dat[u]) u+=1 if v&1: v-=1 score=max(score,self.dat[v]) u//=2 v//=2 return score N=int(input()) A=list(map(int,input().split())) G=[[] for i in range(N+1)] Z=segtree(N+1) h=[] dp=[0]*(N+1) p=[[] for i in range(N+1)] for x in range(1,N+1): y=A[x-1] z=Z.querry(0,y) if z<0: h.append(x) dp[x]=0 Z.update(y,dp[x]*10**6+x) else: count=z//(10**6) pos=z%(10**6) dp[x]=count+1 Z.update(y,dp[x]*10**6+x) for i in range(1,N+1): count=dp[i] p[count].append(i) for i in range(N): if len(p[i])==0: exit() ansx=10**10 ansy=10**10 for x in p[i]: ansx=min(ansx,x) ansy=min(ansy,A[x-1]) print(ansx,ansy)