結果

問題 No.885 アマリクエリ
ユーザー くれちー
提出日時 2019-09-13 22:41:08
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,320 bytes
コンパイル時間 1,197 ms
コンパイル使用メモリ 33,024 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-07-04 10:06:04
合計ジャッジ時間 4,272 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 *nodes;
  size_t n;
} tree_t;

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

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

void tree_recalc_(tree_t t, size_t i) {
  t.nodes[i] = t.nodes[i << 1] + t.nodes[(i << 1) | 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 (t.nodes[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] %= x;
  }
}

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

uint64_t tree_fold(tree_t t) {
  return t.nodes[1];
}

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

  tree_t t = tree_new(n);
  for (size_t i = 0; i < n; ++i)
    scanf("%" SCNu64, tree_node(t, i));

  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