結果
問題 |
No.854 公平なりんご分配
|
ユーザー |
|
提出日時 | 2019-07-26 22:56:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,626 bytes |
コンパイル時間 | 1,936 ms |
コンパイル使用メモリ | 177,696 KB |
実行使用メモリ | 680,064 KB |
最終ジャッジ日時 | 2024-07-02 08:55:44 |
合計ジャッジ時間 | 26,544 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 WA * 60 MLE * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vll = vector<ll>; using vvi = vector<vector<int>>; using vvl = vector<vector<ll>>; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, m; cin >> n; vector<ll> a(n); vector<vector<ll>> rs, srs; vector<ll> zero(n), szero(n + 1); vector<ll> p; int LIM = 3001; vector<bool> used(LIM); for (int i = 2; i < LIM; i++) { if (used[i]) continue; p.push_back(i); for (int j = i; j < LIM; j += i) used[j] = true; } for (int i = 0; i < p.size(); i++) { rs.emplace_back(n); srs.emplace_back(n + 1); } for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] == 0) { zero[i] = 1; continue; } for (int j = 0; j < p.size() && a[i] > 1; j++) { ll c = 0; while (a[i] % p[j] == 0) { a[i] /= p[j]; c++; } rs[j][i] = c; } } for (int i = 0; i < n; i++) szero[i + 1] = szero[i] + zero[i]; for (int i = 0; i < p.size(); i++) for (int j = 0; j < n; j++) srs[i][j + 1] = srs[i][j] + rs[i][j]; cin >> m; for (int i = 0; i < m; i++) { ll l, r, q; cin >> q >> l >> r; l--; bool breaked = false; if (szero[r] - szero[l]) { cout << "NO" << endl; continue; } for (int j = 0; j < p.size() && q > 1; j++) { ll c = 0; while (q % p[j] == 0) { q /= p[j]; c++; } if (srs[j][r] - srs[j][l] < c) { breaked = true; break; } } if (!breaked) cout << "Yes" << endl; else cout << "NO" << endl; } return 0; }