結果

問題 No.121 傾向と対策:門松列(その2)
ユーザー te-shte-sh
提出日時 2017-04-25 15:56:49
言語 D
(dmd 2.105.2)
結果
AC  
実行時間 1,773 ms / 5,000 ms
コード長 1,214 bytes
コンパイル時間 689 ms
コンパイル使用メモリ 95,524 KB
実行使用メモリ 118,760 KB
最終ジャッジ日時 2023-09-03 12:59:49
合計ジャッジ時間 6,833 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
10,228 KB
testcase_01 AC 73 ms
10,860 KB
testcase_02 AC 6 ms
4,380 KB
testcase_03 AC 706 ms
47,800 KB
testcase_04 AC 1,773 ms
118,760 KB
testcase_05 AC 703 ms
48,988 KB
testcase_06 AC 331 ms
46,112 KB
testcase_07 AC 442 ms
45,800 KB
testcase_08 AC 760 ms
48,112 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.d(10): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`

ソースコード

diff #

import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto n = readln.chomp.to!size_t;
  auto ai = readln.split.to!(int[]);

  auto bi = ai.dup.sort().array.uniq.array;
  int[int] ci;
  foreach (int i, b; bi) ci[b] = i + 1;

  auto di = ai.map!(a => ci[a]).array;
  auto maxD = di.maxElement;

  auto bt1 = BiTree!long(maxD);
  bt1.add(di[0], 1);

  auto bt2 = BiTree!long(maxD);
  foreach (d; di[2..$]) bt2.add(d, 1);

  auto ne = bt2.get(di[0]) - bt2.get(di[0] - 1);
  auto r = 0L;

  foreach (i; 1..n-1) {
    auto d1 = di[i], d2 = di[i+1];

    r += bt1.get(d1-1) * bt2.get(d1-1);
    r += (bt1.get(maxD) - bt1.get(d1)) * (bt2.get(maxD) - bt2.get(d1));
    r -= ne - (bt1.get(d1) - bt1.get(d1-1)) * (bt2.get(d1) - bt2.get(d1-1));

    bt1.add(d1, 1);
    ne += bt2.get(d1) - bt2.get(d1-1);
    bt2.add(d2, -1);
    ne -= bt1.get(d2) - bt1.get(d2-1);
  }

  writeln(r);
}

struct BiTree(T)
{
  T[] b; // buffer
  const size_t s; // size

  this(size_t t)
  {
    s = t;
    b = new T[](s + 1);
  }

  pure T get(size_t i) const
  {
    return i ? b[i] + get(i - (i & -i)) : 0;
  }

  void add(size_t i, T v)
  {
    if (i > s) return;
    b[i] += v;
    add(i + (i & -i), v);
  }
}
0