結果
問題 | No.318 学学学学学 |
ユーザー | CHOHCOOH2 |
提出日時 | 2019-07-16 09:37:59 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,485 bytes |
コンパイル時間 | 235 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 89,272 KB |
最終ジャッジ日時 | 2024-05-07 09:47:00 |
合計ジャッジ時間 | 6,809 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
ソースコード
from collections import defaultdict #A,B=map(inr,input().split()) #a=list(map(int,input().split())) from bisect import bisect_left as bl from bisect import bisect_right as br from math import log from fractions import gcd import sys input=sys.stdin.readline N=int(input()) A=list(map(int,input().split())) n=1 while(n<N): n*=2 INF=0 dat=[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 INF eval(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+vr def eval(k,l,r): if lazy[k]!=0:#遅延配列が0かどうか dat[k]=lazy[k] if r-l>1:#最下段かのチェック lazy[2*k+1]=lazy[k]//2 lazy[2*k+2]=lazy[k]//2 lazy[k]=0#伝搬終了 def add(a,b,x,k,l,r): eval(k,l,r) if b<=l or r<=a: return if a<=l and r<=b: lazy[k]+=(r-l)*x eval(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+1 if not(dict2[A[N-1-i]]): dict2[A[N-1-i]]=N-i print(dict1) print(dict2) key=list(dict1.keys()) key.sort() for i in key: s=dict1[i]-1 t=dict2[i]-1 add(s,t+1,i,0,0,n) for i in range(N): print(find(i,i+1,0,0,n),end=" ") print()