結果

問題 No.694 square1001 and Permutation 3
ユーザー ikd
提出日時 2018-06-09 00:28:23
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 2,169 ms / 3,000 ms
コード長 1,922 bytes
コンパイル時間 1,013 ms
コンパイル使用メモリ 115,392 KB
実行使用メモリ 71,088 KB
最終ジャッジ日時 2024-06-13 01:12:08
合計ジャッジ時間 15,690 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

void main(){
import std.stdio, std.string, std.conv, std.algorithm;
int n; rd(n);
auto a=new int[](n);
foreach(i; 0..n) rd(a[i]);
int[int] compress(int[] arr){
int[int] ret;
sort(arr);
foreach(elem; arr){
if((elem in ret)==null) ret[elem]=ret.length.to!(int);
}
return ret;
}
auto map=compress(a.dup);
auto b=new int[](n);
foreach(i; 0..n) b[i]=map[a[i]];
auto freq=new int[](n);
foreach(elem; b) freq[elem]+=1;
auto lb=new long[](n), ub=new long[](n); // lb[i]:=sum(freq[0, i)), ub[i]:=sum(freq(i, n))
foreach(i; 1..n) lb[i]=lb[i-1]+freq[i-1];
foreach_reverse(i; 1..n) ub[i-1]=ub[i]+freq[i];
struct Pair{int val, idx;}
auto arr=new Pair[](n);
foreach(i; 0..n) arr[i]=Pair(b[i], i);
sort!"a.val==b.val ? a.idx>b.idx : a.val>b.val"(arr);
auto tree=new SquareRootDecomposition(n);
long invNum=0;
// writeln(arr);
foreach(e; arr){
int i=e.idx, v=e.val;
invNum+=tree.sum(0, i);
tree.add(i, 1L);
// writeln(invNum);
}
// writeln(invNum);
foreach(e; b){
writeln(invNum);
invNum-=lb[e];
invNum+=ub[e];
}
}
/*
25143 => 5
51432 => 5-1+3=7
14325 => 7-4+0=3
43251 => 3-0+4=7
32514 => 7-3+1=5
*/
class SquareRootDecomposition{
import std.algorithm;
int D=1;
long[] val, buc;
this(int n){
while(D*D<n) D++;
val.length=D*D;
buc.length=D;
}
void add(int i, long x){
val[i]+=x;
buc[i/D]+=x;
}
long sum(int ql, int qr){
long ret=0;
foreach(k; 0..D){
int l=k*D, r=(k+1)*D;
if(r<=ql || qr<=l){
//
}else if(ql<=l && r<=qr){
ret+=buc[k];
}else{
int s=max(l, ql), t=min(r, qr);
ret+=reduce!"a+b"(0L, val[s..t]);
}
}
return ret;
}
}
void rd(T...)(ref T x){
import std.stdio, std.string, std.conv;
auto l=readln.split;
assert(l.length==x.length);
foreach(i, ref e; x) e=l[i].to!(typeof(e));
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0