結果

問題 No.694 square1001 and Permutation 3
コンテスト
ユーザー ikd
提出日時 2018-06-09 00:17:17
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 1,933 bytes
コンパイル時間 843 ms
コンパイル使用メモリ 115,600 KB
実行使用メモリ 74,316 KB
最終ジャッジ日時 2024-06-13 01:10:37
合計ジャッジ時間 12,340 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 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) ret[elem]++;
      else 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, 1);
    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, int 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));
}
0