結果

問題 No.694 square1001 and Permutation 3
ユーザー ikdikd
提出日時 2018-06-09 00:28:23
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 2,008 ms / 3,000 ms
コード長 1,922 bytes
コンパイル時間 1,504 ms
コンパイル使用メモリ 100,988 KB
実行使用メモリ 71,788 KB
最終ジャッジ日時 2023-09-03 20:22:34
合計ジャッジ時間 14,814 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,384 KB
testcase_06 AC 1 ms
4,384 KB
testcase_07 AC 1,617 ms
27,564 KB
testcase_08 AC 1,824 ms
30,812 KB
testcase_09 AC 2,008 ms
71,544 KB
testcase_10 AC 1,527 ms
28,484 KB
testcase_11 AC 1,976 ms
71,612 KB
testcase_12 AC 1,954 ms
71,788 KB
testcase_13 AC 2 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

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));
}
0