結果

問題 No.885 アマリクエリ
コンテスト
ユーザー risujiroh
提出日時 2019-09-13 22:55:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 786 ms / 2,000 ms
コード長 4,697 bytes
コンパイル時間 1,731 ms
コンパイル使用メモリ 177,312 KB
実行使用メモリ 44,416 KB
最終ジャッジ日時 2024-07-04 10:14:38
合計ジャッジ時間 5,089 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<class Z> Z rng(Z a, Z b) {
  static mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<Z>(a, b - 1)(mt);
}
namespace RBSTMap {
  constexpr int lim = 1 << 20;
  using Key = int;
  auto comp = greater<Key>();
  using T = int;
  constexpr T e = 0;
  T op(const T& a, const T& b) { return a + b; }
  T op(const T& a, const T& b, const T& c) { return op(op(a, b), c); }

  struct Node;
  using Tree = Node*;
  struct Node {
    Tree lch, rch;
    int sz, h;
    Key key;
    T val, acc = e;
  };
  Tree nil = new Node();

  Tree update(Tree t) {
    t->sz = t->lch->sz + 1 + t->rch->sz;
    t->h = max(t->lch->h, t->rch->h) + 1;
    t->acc = op(t->lch->acc, t->val, t->rch->acc);
    return t;
  }
  Node pool[lim];
  Tree make(const Key& k, const T& v, Tree l, Tree r) {
    static int p = 0;
    assert(p < lim);
    Tree t = pool + p++;
    t->lch = l, t->rch = r;
    t->key = k, t->val = v;
    return update(t);
  }

  Tree merge(Tree l, Tree r) {
    if (l == nil) return r;
    if (r == nil) return l;
    if (rng(0, l->sz + r->sz) < l->sz) {
      l->rch = merge(l->rch, r);
      return update(l);
    } else {
      r->lch = merge(l, r->lch);
      return update(r);
    }
  }
  Tree merge(Tree l, Tree m, Tree r) { return merge(merge(l, m), r); }
  pair<Tree, Tree> lower_split(Tree t, const Key& k) {
    if (t == nil) return {nil, nil};
    if (comp(t->key, k)) {
      Tree r;
      tie(t->rch, r) = lower_split(t->rch, k);
      return {update(t), r};
    } else {
      Tree l;
      tie(l, t->lch) = lower_split(t->lch, k);
      return {l, update(t)};
    }
  }
  pair<Tree, Tree> upper_split(Tree t, const Key& k) {
    if (t == nil) return {nil, nil};
    if (comp(k, t->key)) {
      Tree l;
      tie(l, t->lch) = upper_split(t->lch, k);
      return {l, update(t)};
    } else {
      Tree r;
      tie(t->rch, r) = upper_split(t->rch, k);
      return {update(t), r};
    }
  }
  tuple<Tree, Tree, Tree> split(Tree t, const Key& k) {
    Tree l, m, r;
    tie(l, r) = lower_split(t, k);
    tie(m, r) = upper_split(r, k);
    return make_tuple(l, m, r);
  }

  void insert(Tree& t, const Key& k, const T& v) {
    if (!rng(0, t->sz + 1)) {
      Tree l, r;
      tie(l, ignore, r) = split(t, k);
      t = make(k, v, l, r);
      return;
    }
    if (comp(k, t->key)) {
      insert(t->lch, k, v);
    } else if (comp(t->key, k)) {
      insert(t->rch, k, v);
    } else {
      t->key = k, t->val = v;
    }
    t = update(t);
  }
  void erase(Tree& t, const Key& k) {
    if (t == nil) return;
    if (comp(k, t->key)) {
      erase(t->lch, k);
      t = update(t);
    } else if (comp(t->key, k)) {
      erase(t->rch, k);
      t = update(t);
    } else {
      t = merge(t->lch, t->rch);
    }
  }
  int lower_bound(Tree t, const Key& k) {
    if (t == nil) return 0;
    if (comp(t->key, k)) return t->lch->sz + 1 + lower_bound(t->rch, k);
    return lower_bound(t->lch, k);
  }
  int upper_bound(Tree t, const Key& k) {
    if (t == nil) return 0;
    if (comp(k, t->key)) return upper_bound(t->lch, k);
    return t->lch->sz + 1 + upper_bound(t->rch, k);
  }
  int count(Tree t, const Key& k) { return upper_bound(t, k) - lower_bound(t, k); }

  pair<Key, T> get(Tree t, int i) {
    assert(0 <= i and i < t->sz);
    if (i == t->lch->sz) return {t->key, t->val};
    if (i < t->lch->sz) return get(t->lch, i);
    return get(t->rch, i - t->lch->sz - 1);
  }
  T at(Tree& t, const Key& k) {
    if (!count(t, k)) {
      insert(t, k, e);
      return e;
    }
    return get(t, lower_bound(t, k)).second;
  }
  T acc(Tree t, int l, int r) {
    if (l <= 0 and t->sz <= r) return t->acc;
    T resl = l < t->lch->sz ? acc(t->lch, l, r) : e;
    T resr = t->lch->sz + 1 < r ? acc(t->rch, l - t->lch->sz - 1, r - t->lch->sz - 1) : e;
    T resm = l <= t->lch->sz and t->lch->sz < r ? t->val : e;
    return op(resl, resm, resr);
  }
}

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  auto mp = RBSTMap::nil;
  while (n--) {
    int a; cin >> a;
    insert(mp, a, at(mp, a) + 1);
  }
  lint res = 0;
  for (int i = 0; i < mp->sz; ++i) {
    auto e = get(mp, i);
    res += (lint)e.first * e.second;
  }
  int m; cin >> m;
  while (m--) {
    int x; cin >> x;
    while (true) {
      auto e = get(mp, 0);
      if (e.first < x) break;
      erase(mp, e.first);
      insert(mp, e.first % x, at(mp, e.first % x) + e.second);
      res -= (lint)(e.first - e.first % x) * e.second;
    }
    cout << res << '\n';
  }
}
0