結果
問題 |
No.2758 RDQ
|
ユーザー |
|
提出日時 | 2024-05-18 00:02:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 647 ms / 2,000 ms |
コード長 | 1,086 bytes |
コンパイル時間 | 2,335 ms |
コンパイル使用メモリ | 140,956 KB |
実行使用メモリ | 15,232 KB |
最終ジャッジ日時 | 2024-12-20 15:51:25 |
合計ジャッジ時間 | 9,174 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <unordered_map> #include <ranges> std::vector<int> div(const int n) { std::vector<int> d; for(int64_t i = 1; i * i <= n; ++i) { if(n % i == 0) { d.emplace_back(i); if(i * i != n) { d.emplace_back(n / i); } } } std::ranges::sort(d); return d; } int main() { std::cin.tie(nullptr) -> sync_with_stdio(false); int n, q; std::cin >> n >> q; std::vector<int> a(n); for(auto &el: a) { std::cin >> el; } std::unordered_map<int, std::vector<int>> cnt; for(const auto i: std::ranges::iota_view(0, n)) { for(const auto d: div(a[i])) { cnt[d].emplace_back(i); } } while(q--) { int l, r, k; std::cin >> l >> r >> k; if(!cnt.contains(k)) { std::cout << 0 << '\n'; continue; } const auto b = cnt[k]; std::cout << std::ranges::lower_bound(b, r) - std::ranges::lower_bound(b, l - 1) << '\n'; } }