結果
問題 | No.854 公平なりんご分配 |
ユーザー |
![]() |
提出日時 | 2019-07-26 22:38:40 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 658 ms / 3,153 ms |
コード長 | 1,738 bytes |
コンパイル時間 | 774 ms |
コンパイル使用メモリ | 77,904 KB |
実行使用メモリ | 246,028 KB |
最終ジャッジ日時 | 2024-07-02 08:06:03 |
合計ジャッジ時間 | 14,351 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 92 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:42:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 42 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:43:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 43 | for(int i = 1; i <= n; i++) scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <stdio.h> #include <stdlib.h> #include <unordered_map> #define llint long long using namespace std; int n, Q; int a[100005]; int d[325][100005]; int sum[325][100005]; unordered_map<int, int> mp, fmp[2005]; bool prime[2005]; vector<llint> pvec; int main(void) { for(int i = 2; i < 55; i++){ if(prime[i]) continue; for(int j = 2*i; j < 2005; j+=i) prime[j] = true; } for(int i = 2; i < 2005; i++){ if(!prime[i]) pvec.push_back(i); } int m = pvec.size(); for(int i = 1; i < 2005; i++){ for(int j = 0; j < m; j++){ int t = i; while(t % pvec[j] == 0){ fmp[i][j]++; t /= pvec[j]; } } } scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++){ for(auto it = fmp[a[i]].begin(); it != fmp[a[i]].end(); it++) d[it->first][i] = it->second; } for(int i = 0; i < m; i++){ for(int j = 1; j <= n; j++) sum[i][j] = sum[i][j-1] + d[i][j]; } for(int i = 1; i <= n; i++){ if(a[i] == 0) d[320][i] = 1; } for(int i = 1; i <= n; i++){ sum[320][i] = sum[320][i-1] + d[320][i]; } cin >> Q; int p, l, r; for(int q = 0; q < Q; q++){ cin >> p >> l >> r; if(sum[320][r]-sum[320][l-1] > 0){ printf("Yes\n"); continue; } mp.clear(); int t = p; for(int i = 0; i < m; i++){ if(pvec[i] > t) break; while(t % pvec[i] == 0){ mp[i]++; t /= pvec[i]; } } if(t > 1){ printf("NO\n"); continue; } bool flag = true; for(auto it = mp.begin(); it != mp.end(); it++){ if(it->second > sum[it->first][r]-sum[it->first][l-1]){ flag = false; break; } } if(flag) printf("Yes\n"); else printf("NO\n"); } return 0; }