結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2019-07-16 09:41:06 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,459 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 88,832 KB |
最終ジャッジ日時 | 2024-11-30 01:31:18 |
合計ジャッジ時間 | 6,523 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 26 |
ソースコード
from collections import defaultdict#A,B=map(inr,input().split())#a=list(map(int,input().split()))from bisect import bisect_left as blfrom bisect import bisect_right as brfrom math import logfrom fractions import gcdimport sysinput=sys.stdin.readlineN=int(input())A=list(map(int,input().split()))n=1while(n<N):n*=2INF=0dat=[INF]*(2*n-1)lazy=[0]*(2*n-1)def find(a,b,k,l,r):#O()(logn)^2)if r<=a or b<=l:return INFeval(k,l,r)#O(logn)if a<=l and r<=b:return dat[k]else:vl=find(a,b,k*2+1,l,(l+r)//2)vr=find(a,b,k*2+2,(l+r)//2,r)return vl+vrdef eval(k,l,r):if lazy[k]!=0:#遅延配列が0かどうかdat[k]=lazy[k]if r-l>1:#最下段かのチェックlazy[2*k+1]=lazy[k]//2lazy[2*k+2]=lazy[k]//2lazy[k]=0#伝搬終了def add(a,b,x,k,l,r):eval(k,l,r)if b<=l or r<=a:returnif a<=l and r<=b:lazy[k]+=(r-l)*xeval(k,l,r)else:add(a,b,x,2*k+1,l,(l+r)//2)add(a,b,x,2*k+2,(l+r)//2,r)dat[k]=dat[2*k+1]+dat[2*k+2]dict1=defaultdict(int)dict2=defaultdict(int)for i in range(N):if not(dict1[A[i]]):dict1[A[i]]=i+1if not(dict2[A[N-1-i]]):dict2[A[N-1-i]]=N-ikey=list(dict1.keys())key.sort()for i in key:s=dict1[i]-1t=dict2[i]-1add(s,t+1,i,0,0,n)for i in range(N):print(find(i,i+1,0,0,n),end=" ")print()