結果
問題 | No.694 square1001 and Permutation 3 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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 => 551432 => 5-1+3=714325 => 7-4+0=343251 => 3-0+4=732514 => 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));}