結果

問題 No.885 アマリクエリ
コンテスト
ユーザー くれちー
提出日時 2019-09-13 23:30:22
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,035 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 33,664 KB
実行使用メモリ 13,884 KB
最終ジャッジ日時 2024-07-04 10:30:43
合計ジャッジ時間 4,548 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx")

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  uint64_t a;
  size_t n;
} node_t;

typedef struct {
  node_t *nodes;
  size_t n;
} tree_t;

tree_t tree_new(size_t n) {
  return (tree_t) {
    .nodes = (node_t *)calloc(n * 2, sizeof(node_t)),
    .n = n,
  };
}

node_t *tree_node(tree_t t, size_t i) {
  return &t.nodes[t.n + i];
}

uint64_t tree_value_(tree_t t, size_t i) {
  return t.nodes[i].a * t.nodes[i].n;
}

void tree_recalc_(tree_t t, size_t i) {
  t.nodes[i] = (node_t) {
    .a = tree_value_(t, i << 1) + tree_value_(t, (i << 1) | 1),
    .n = 1,
  };
}

void tree_build(tree_t t) {
  for (size_t i = t.n - 1; i >= 1; --i)
    tree_recalc_(t, i);
}

void tree_act_(tree_t t, size_t i, uint64_t x) {
  if (tree_value_(t, i) < x)
    return;
  if (i < t.n) {
    tree_act_(t, i << 1, x);
    tree_act_(t, (i << 1) | 1, x);
    tree_recalc_(t, i);
  } else {
    t.nodes[i].a %= x;
  }
}

void tree_act(tree_t t, uint64_t x) {
  tree_act_(t, 1, x);
}

uint64_t tree_fold(tree_t t) {
  return tree_value_(t, 1);
}

int compar(const void *a, const void *b) {
  uint64_t a_ = *(uint64_t *)a;
  uint64_t b_ = *(uint64_t *)b;
  return a_ == b_ ? 0 : (a_ < b_ ? -1 : 1);
}

int main(void) {
  size_t n;
  scanf("%zu", &n);

  uint64_t *a = (uint64_t *)calloc(n, sizeof(uint64_t));
  for (size_t i = 0; i < n; ++i)
    scanf("%" SCNu64, &a[i]);

  qsort(a, n, sizeof(uint64_t), compar);

  tree_t t = tree_new(n);

  {
    size_t j = 0;
    size_t m = 1;
    for (size_t i = 0; i < n; ++i) {
      if (i + 1 < n && a[i] == a[i + 1]) {
        ++m;
        continue;
      }
      *tree_node(t, j) = (node_t) {
        .a = a[i],
        .n = m,
      };
      ++j;
      m = 1;
    }
  }

  tree_build(t);

  size_t q;
  scanf("%zu", &q);

  for (size_t i = 0; i < q; ++i) {
    uint64_t x;
    scanf("%" SCNu64, &x);
    tree_act(t, x);
    printf("%" PRIu64 "\n", tree_fold(t));
  }
}
0