結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー te-sh
提出日時 2017-12-22 13:56:36
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 2,324 bytes
コンパイル時間 1,120 ms
コンパイル使用メモリ 152,816 KB
実行使用メモリ 18,108 KB
最終ジャッジ日時 2024-06-12 23:14:58
合計ジャッジ時間 9,219 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 38
権限があれば一括ダウンロードができます

ソースコード

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 nnids = za1.length.to!int;

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

  auto acs = new int[](n), scores = new int[](nnids), vscs = [0];
  foreach (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;
    vscs ~= scores[nid];
  }

  int[int] za2;
  auto id2 = 0;
  foreach (vsc; vscs.sort().uniq) za2[vsc] = id2++;
  auto nvscs = za2.length.to!int;

  auto btb = BiTree!int(nvscs), btcs = new BiTree!int[](nvscs);
  foreach (ref btc; btcs) btc = BiTree!int(4);

  auto rankInScore = new int[](nnids);
  acs[] = 0; scores[] = 0;
  foreach (nid, pi; lockstep(nids, p)) {
    if (pi != -1) {
      acs[pi]++;
      auto pt = 50*l[pi] + 500*l[pi]/(8+2*acs[pi]);

      auto psc = za2[scores[nid]];
      if (psc > 0) {
        btb[psc] += -1;
        btcs[psc][rankInScore[nid]] += -1;
      }

      scores[nid] += pt;
      auto nsc = za2[scores[nid]];
      rankInScore[nid] = btb[nsc];
      btb[nsc] += 1;
      btcs[nsc][rankInScore[nid]] += 1;
    } else {
      auto sc = za2[scores[nid]];
      writeln(btb[sc+1..$] + btcs[sc][0..rankInScore[nid]] + 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