結果
問題 | No.854 公平なりんご分配 |
ユーザー | Sumitacchan |
提出日時 | 2019-07-26 22:09:16 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,100 ms / 3,153 ms |
コード長 | 3,842 bytes |
コンパイル時間 | 1,984 ms |
コンパイル使用メモリ | 174,696 KB |
実行使用メモリ | 243,200 KB |
最終ジャッジ日時 | 2023-09-15 01:45:06 |
合計ジャッジ時間 | 23,769 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,384 KB |
testcase_15 | AC | 1 ms
4,384 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 2 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 6 ms
4,380 KB |
testcase_23 | AC | 6 ms
4,416 KB |
testcase_24 | AC | 10 ms
5,456 KB |
testcase_25 | AC | 5 ms
4,380 KB |
testcase_26 | AC | 10 ms
5,456 KB |
testcase_27 | AC | 9 ms
5,352 KB |
testcase_28 | AC | 5 ms
4,380 KB |
testcase_29 | AC | 3 ms
4,376 KB |
testcase_30 | AC | 5 ms
4,380 KB |
testcase_31 | AC | 10 ms
5,112 KB |
testcase_32 | AC | 136 ms
54,224 KB |
testcase_33 | AC | 118 ms
30,008 KB |
testcase_34 | AC | 239 ms
73,832 KB |
testcase_35 | AC | 172 ms
57,892 KB |
testcase_36 | AC | 74 ms
6,248 KB |
testcase_37 | AC | 129 ms
50,552 KB |
testcase_38 | AC | 101 ms
41,720 KB |
testcase_39 | AC | 326 ms
77,600 KB |
testcase_40 | AC | 125 ms
25,980 KB |
testcase_41 | AC | 160 ms
46,944 KB |
testcase_42 | AC | 219 ms
72,444 KB |
testcase_43 | AC | 221 ms
49,560 KB |
testcase_44 | AC | 250 ms
66,372 KB |
testcase_45 | AC | 186 ms
15,224 KB |
testcase_46 | AC | 301 ms
66,476 KB |
testcase_47 | AC | 123 ms
37,564 KB |
testcase_48 | AC | 208 ms
71,444 KB |
testcase_49 | AC | 201 ms
72,780 KB |
testcase_50 | AC | 122 ms
50,556 KB |
testcase_51 | AC | 310 ms
69,092 KB |
testcase_52 | AC | 168 ms
31,548 KB |
testcase_53 | AC | 103 ms
30,972 KB |
testcase_54 | AC | 173 ms
36,768 KB |
testcase_55 | AC | 81 ms
31,292 KB |
testcase_56 | AC | 81 ms
32,644 KB |
testcase_57 | AC | 101 ms
26,840 KB |
testcase_58 | AC | 157 ms
12,648 KB |
testcase_59 | AC | 64 ms
23,952 KB |
testcase_60 | AC | 123 ms
26,788 KB |
testcase_61 | AC | 49 ms
7,564 KB |
testcase_62 | AC | 137 ms
23,144 KB |
testcase_63 | AC | 100 ms
24,412 KB |
testcase_64 | AC | 41 ms
10,932 KB |
testcase_65 | AC | 165 ms
64,064 KB |
testcase_66 | AC | 82 ms
18,116 KB |
testcase_67 | AC | 151 ms
41,436 KB |
testcase_68 | AC | 123 ms
19,188 KB |
testcase_69 | AC | 180 ms
77,460 KB |
testcase_70 | AC | 69 ms
26,508 KB |
testcase_71 | AC | 79 ms
28,672 KB |
testcase_72 | AC | 97 ms
6,420 KB |
testcase_73 | AC | 129 ms
51,820 KB |
testcase_74 | AC | 207 ms
63,000 KB |
testcase_75 | AC | 104 ms
28,856 KB |
testcase_76 | AC | 155 ms
49,560 KB |
testcase_77 | AC | 198 ms
70,136 KB |
testcase_78 | AC | 165 ms
21,220 KB |
testcase_79 | AC | 179 ms
43,464 KB |
testcase_80 | AC | 173 ms
45,828 KB |
testcase_81 | AC | 142 ms
46,908 KB |
testcase_82 | AC | 707 ms
242,196 KB |
testcase_83 | AC | 1,054 ms
242,276 KB |
testcase_84 | AC | 1,039 ms
242,248 KB |
testcase_85 | AC | 1,081 ms
242,164 KB |
testcase_86 | AC | 337 ms
243,200 KB |
testcase_87 | AC | 707 ms
242,264 KB |
testcase_88 | AC | 705 ms
242,264 KB |
testcase_89 | AC | 708 ms
242,252 KB |
testcase_90 | AC | 707 ms
242,272 KB |
testcase_91 | AC | 710 ms
242,172 KB |
testcase_92 | AC | 1,091 ms
242,244 KB |
testcase_93 | AC | 1,100 ms
242,264 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; #define FOR(i, begin, end) for(int i=(begin);i<(end);i++) #define REP(i, n) FOR(i,0,n) #define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--) #define IREP(i, n) IFOR(i,0,n) #define Sort(v) sort(v.begin(), v.end()) #define Reverse(v) reverse(v.begin(), v.end()) #define all(v) v.begin(),v.end() #define SZ(v) ((int)v.size()) #define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x)) #define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x)) #define Max(a, b) a = max(a, b) #define Min(a, b) a = min(a, b) #define bit_exist(x, n) ((x >> n) & 1) #define debug(x) cout << #x << "=" << x << endl; #define vdebug(v) cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; #define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} #define pb push_back #define f first #define s second #define int long long #define INF 1000000000000000000 template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; } template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; } template<typename T> void Out(T x) { cout << x << endl; } template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); } using vec = vector<int>; using mat = vector<vec>; using Pii = pair<int, int>; using PiP = pair<int, Pii>; using PPi = pair<Pii, int>; using bools = vector<bool>; using pairs = vector<Pii>; //int dx[4] = {1,0,-1,0}; //int dy[4] = {0,1,0,-1}; //char d[4] = {'D','R','U','L'}; const int mod = 1000000007; //const int mod = 998244353; #define Add(x, y) x = (x + (y)) % mod #define Mult(x, y) x = (x * (y)) % mod class BIT { public: vector<int> bit; int M; BIT(int M): bit(vector<int>(M+1, 0)), M(M) {} int sum(int i) { if (!i) return 0; return bit[i] + sum(i-(i&-i)); } void add(int i, int x) { if (i > M) return; bit[i] += x; add(i+(i&-i), x); } }; vec prime_list(int MAX_N){ vector<bool> is_prime(MAX_N + 1, true); vec prime(0); is_prime[0] = false; is_prime[1] = false; FOR(i, 2, MAX_N + 1){ if(is_prime[i]){ prime.push_back(i); int tmp = i * 2; while(tmp <= MAX_N){ is_prime[tmp] = false; tmp += i; } } } return prime; } signed main(){ int N; cin >> N; vec A(N); cin >> A; vec p = prime_list(2000); //debug(SZ(p)); int n = SZ(p); vector<BIT> b(n, BIT(N)); vec zero; REP(i, N){ if(A[i] != 0){ REP(j, n){ int c = 0; while(A[i] % p[j] == 0){ c++; A[i] /= p[j]; } if(c) b[j].add(i + 1, c); } }else{ zero.pb(i + 1); } } int Q; cin >> Q; int P, L, R; bools ans(Q); REP(q, Q){ cin >> P >> L >> R; ans[q] = true; int i0 = Lower_bound(zero, L); if(i0 < SZ(zero) && zero[i0] <= R) continue; REP(j, n){ int c = 0; while(P % p[j] == 0){ c++; P /= p[j]; } if(c > 0 && c > b[j].sum(R) - b[j].sum(L - 1)){ ans[q] = false; break; } } if(P > 1) ans[q] = false; } REP(q, Q) Ans(ans[q], "Yes", "NO"); return 0; }