結果
問題 | No.885 アマリクエリ |
ユーザー | keijak |
提出日時 | 2021-05-23 16:38:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 200 ms / 2,000 ms |
コード長 | 1,725 bytes |
コンパイル時間 | 661 ms |
コンパイル使用メモリ | 61,440 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-27 03:50:39 |
合計ジャッジ時間 | 2,604 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 200 ms
6,812 KB |
testcase_01 | AC | 55 ms
6,940 KB |
testcase_02 | AC | 33 ms
6,944 KB |
testcase_03 | AC | 24 ms
6,940 KB |
testcase_04 | AC | 25 ms
6,940 KB |
testcase_05 | AC | 19 ms
6,944 KB |
testcase_06 | AC | 18 ms
6,944 KB |
testcase_07 | AC | 6 ms
6,944 KB |
testcase_08 | AC | 15 ms
6,944 KB |
testcase_09 | AC | 58 ms
6,940 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 1 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 1 ms
6,940 KB |
testcase_20 | AC | 1 ms
6,940 KB |
testcase_21 | AC | 2 ms
6,944 KB |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <algorithm> #include <cctype> #include <cstdio> #include <type_traits> #include <vector> #define REP_(i, a_, b_, a, b, ...) \ for (int i = (a), END_##i = (b); i < END_##i; ++i) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) using i64 = long long; struct Input { inline operator int() { return read_int<int>(); } inline operator long long() { return read_int<long long>(); } inline operator unsigned() { return read_int<unsigned>(); } private: template <typename T> static T read_int() { T ret = 0, sgn = 1; int ch = getchar_unlocked(); while (isspace(ch)) { ch = getchar_unlocked(); } if constexpr (!std::is_unsigned<T>::value) { if (ch == '-') { sgn = -1; ch = getchar_unlocked(); } } for (; ('0' <= ch) & (ch <= '9'); ch = getchar_unlocked()) { ret = (ret * 10) + (ch - '0'); } ungetc(ch, stdin); if constexpr (std::is_unsigned<T>::value) { return ret; } else { return ret * sgn; } } } input; using namespace std; int main() { const int n = input; vector<i64> a(n); REP(i, n) a[i] = input; const int Q = input; vector<i64> X(Q); REP(i, Q) X[i] = input; REP(i, 1, Q) { X[i] = min(X[i], X[i - 1]); } vector<i64> ans(Q + 1, 0); REP(i, n) { i64 p = a[i]; int j = 0; while (true) { int q = lower_bound(X.begin() + j, X.end(), p, greater{}) - X.begin(); ans[j] += p; ans[q] -= p; if (q == Q) break; p %= X[j]; j = q; } } REP(i, 1, Q + 1) { ans[i] += ans[i - 1]; } REP(i, Q) { printf("%lld\n", ans[i]); } }