結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー te-shte-sh
提出日時 2017-12-22 14:19:28
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 192 ms / 5,000 ms
コード長 2,218 bytes
コンパイル時間 1,050 ms
コンパイル使用メモリ 153,088 KB
実行使用メモリ 22,784 KB
最終ジャッジ日時 2024-06-12 23:15:12
合計ジャッジ時間 8,648 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 151 ms
14,080 KB
testcase_13 AC 192 ms
18,048 KB
testcase_14 AC 177 ms
16,128 KB
testcase_15 AC 174 ms
19,328 KB
testcase_16 AC 161 ms
17,536 KB
testcase_17 AC 163 ms
17,152 KB
testcase_18 AC 145 ms
14,208 KB
testcase_19 AC 155 ms
16,384 KB
testcase_20 AC 162 ms
16,256 KB
testcase_21 AC 173 ms
18,048 KB
testcase_22 AC 175 ms
18,048 KB
testcase_23 AC 149 ms
13,952 KB
testcase_24 AC 174 ms
17,024 KB
testcase_25 AC 142 ms
12,416 KB
testcase_26 AC 132 ms
10,752 KB
testcase_27 AC 164 ms
18,304 KB
testcase_28 AC 170 ms
18,432 KB
testcase_29 AC 159 ms
16,128 KB
testcase_30 AC 168 ms
18,816 KB
testcase_31 AC 160 ms
18,048 KB
testcase_32 AC 160 ms
16,000 KB
testcase_33 AC 167 ms
17,408 KB
testcase_34 AC 141 ms
12,672 KB
testcase_35 AC 170 ms
19,456 KB
testcase_36 AC 140 ms
12,416 KB
testcase_37 AC 165 ms
21,888 KB
testcase_38 AC 146 ms
17,920 KB
testcase_39 AC 120 ms
17,792 KB
testcase_40 AC 119 ms
17,920 KB
testcase_41 AC 182 ms
22,784 KB
testcase_42 AC 172 ms
22,784 KB
testcase_43 AC 135 ms
14,464 KB
testcase_44 AC 134 ms
18,304 KB
testcase_45 AC 144 ms
22,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

void main()
{
  auto n = readln.chomp.to!int;
  auto l = readln.split.to!(int[]);
  auto t = readln.chomp.to!int;
  auto names = new string[](t), p = new int[](t);
  foreach (i; 0..t) {
    auto rd = readln.splitter;
    names[i] = rd.front; rd.popFront();
    auto pi = rd.front[0];
    p[i] = pi == '?' ? -1 : cast(int)(pi-'A');
  }

  int[string] za1;
  auto id1 = 0;
  foreach (name; names.dup.sort().uniq) za1[name] = id1++;

  auto nids = new int[](t);
  foreach (i; 0..t) nids[i] = za1[names[i]];
  auto nnids = za1.length.to!int;

  auto acs = new int[](n), scores = new int[](nnids);
  Score[] vscores;
  foreach (i, nid, pi; lockstep(nids, p)) {
    if (pi == -1) continue;
    acs[pi]++;
    auto pt = 50*l[pi] + 500*l[pi]/(8+2*acs[pi]);
    scores[nid] += pt;
    vscores ~= Score(scores[nid], i);
  }

  int[size_t][int] za2;
  auto id2 = 0;
  foreach (vscore; vscores.sort()) za2[vscore.pt][vscore.i] = id2++;

  auto bt = BiTree!int(vscores.length), lastAc = new size_t[](nnids);
  acs[] = 0; scores[] = 0;
  foreach (i, nid, pi; lockstep(nids, p)) {
    if (pi != -1) {
      if (scores[nid] > 0) bt[za2[scores[nid]][lastAc[nid]]] += -1;
      acs[pi]++;
      auto pt = 50*l[pi] + 500*l[pi]/(8+2*acs[pi]);
      scores[nid] += pt;
      bt[za2[scores[nid]][i]] += 1;
      lastAc[nid] = i;
    } else {
      writeln(bt[za2[scores[nid]][lastAc[nid]]..$]);
    }
  }
}

struct Score
{
  int pt;
  size_t i;

  auto opCmp(Score rhs)
  {
    return pt > rhs.pt ? 1 : pt < rhs.pt ? -1 : i < rhs.i ? 1 : -1;
  }
}

struct BiTree(T)
{
  size_t n;
  T[] buf;

  this(size_t n)
  {
    this.n = n;
    this.buf = new T[](n + 1);
  }

  void opIndexOpAssign(string op: "+")(T val, size_t i)
  {
    if (i > n) {
      n *= 2;
      buf.length = n+1;
    }

    ++i;
    for (; i <= n; i += i & -i)
      buf[i] += val;
  }

  pure T opSlice(size_t r, size_t l) const
  {
    return get(l) - get(r);
  }

  pure size_t opDollar() const { return n; }
  pure T opIndex(size_t i) const { return opSlice(i, i+1); }

private:

  pure T get(size_t i) const
  {
    auto s = T(0);
    for (; i > 0; i -= i & -i)
      s += buf[i];
    return s;
  }
}
0