結果
問題 | No.121 傾向と対策:門松列(その2) |
ユーザー | gigurururu |
提出日時 | 2015-01-10 01:33:49 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 4,187 ms / 5,000 ms |
コード長 | 899 bytes |
コンパイル時間 | 2,021 ms |
コンパイル使用メモリ | 77,436 KB |
実行使用メモリ | 276,648 KB |
最終ジャッジ日時 | 2023-09-11 04:02:12 |
合計ジャッジ時間 | 16,184 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 200 ms
85,464 KB |
testcase_01 | AC | 264 ms
89,280 KB |
testcase_02 | AC | 111 ms
80,368 KB |
testcase_03 | AC | 947 ms
262,504 KB |
testcase_04 | AC | 4,187 ms
249,124 KB |
testcase_05 | AC | 1,072 ms
267,608 KB |
testcase_06 | AC | 1,671 ms
276,648 KB |
testcase_07 | AC | 2,125 ms
256,952 KB |
testcase_08 | AC | 2,027 ms
261,396 KB |
ソースコード
# LayCurseさん想定解 http://yukicoder.me/submissions/8162 の写経 class BIT: def __init__(self,n):self.n=n;self.buf=[0]*n def add(self,x,v): while x<self.n:self.buf[x]+=v;x|=x+1 def sum(self,x): s=0 while x>=0:s+=self.buf[x];x=(x&(x+1))-1 return s def range(self,a,b):return self.sum(b if b>=0 else self.n)-self.sum(a-1) N=input() tmp=sorted(zip(map(int,raw_input().split()),range(N))) A=[i for i,j in tmp] ind=[j for i,j in tmp] t=BIT(N) res=0 st=0 while st<N: arr=[ind[st]] sz=1 while((st+1<N)and(A[st]==A[st+1])):st+=1;arr.append(ind[st]) sz=len(arr) for i in range(sz): x=t.sum(arr[i]-1) y=t.range(arr[i]+1,N-1) if arr[i]+1<N else 0 res+=x*y+(arr[i]-x-i)*(N-arr[i]-1-y-(sz-i-1)) for i in range(sz):t.add(arr[i],1) for i in range(1,sz):res-=(arr[i]-arr[i-1]-1)*i*(sz-i) st+=1 print res