結果
問題 | No.854 公平なりんご分配 |
ユーザー | beet |
提出日時 | 2019-07-26 21:43:10 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,365 ms / 3,153 ms |
コード長 | 4,479 bytes |
コンパイル時間 | 2,803 ms |
コンパイル使用メモリ | 228,928 KB |
実行使用メモリ | 47,652 KB |
最終ジャッジ日時 | 2023-09-15 00:59:36 |
合計ジャッジ時間 | 16,645 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,892 KB |
testcase_01 | AC | 5 ms
7,096 KB |
testcase_02 | AC | 3 ms
7,204 KB |
testcase_03 | AC | 3 ms
6,956 KB |
testcase_04 | AC | 4 ms
6,892 KB |
testcase_05 | AC | 3 ms
6,896 KB |
testcase_06 | AC | 3 ms
7,188 KB |
testcase_07 | AC | 3 ms
6,972 KB |
testcase_08 | AC | 3 ms
6,992 KB |
testcase_09 | AC | 4 ms
6,948 KB |
testcase_10 | AC | 4 ms
6,952 KB |
testcase_11 | AC | 3 ms
6,952 KB |
testcase_12 | AC | 4 ms
6,936 KB |
testcase_13 | AC | 4 ms
7,020 KB |
testcase_14 | AC | 4 ms
6,896 KB |
testcase_15 | AC | 3 ms
6,952 KB |
testcase_16 | AC | 3 ms
7,052 KB |
testcase_17 | AC | 3 ms
7,200 KB |
testcase_18 | AC | 4 ms
6,948 KB |
testcase_19 | AC | 4 ms
6,896 KB |
testcase_20 | AC | 3 ms
6,972 KB |
testcase_21 | AC | 4 ms
6,992 KB |
testcase_22 | AC | 6 ms
7,440 KB |
testcase_23 | AC | 5 ms
7,204 KB |
testcase_24 | AC | 7 ms
7,164 KB |
testcase_25 | AC | 4 ms
7,232 KB |
testcase_26 | AC | 7 ms
7,324 KB |
testcase_27 | AC | 6 ms
7,548 KB |
testcase_28 | AC | 5 ms
6,964 KB |
testcase_29 | AC | 4 ms
7,056 KB |
testcase_30 | AC | 5 ms
7,216 KB |
testcase_31 | AC | 7 ms
7,212 KB |
testcase_32 | AC | 40 ms
14,812 KB |
testcase_33 | AC | 48 ms
11,540 KB |
testcase_34 | AC | 89 ms
18,572 KB |
testcase_35 | AC | 59 ms
15,872 KB |
testcase_36 | AC | 46 ms
8,348 KB |
testcase_37 | AC | 38 ms
14,372 KB |
testcase_38 | AC | 29 ms
13,044 KB |
testcase_39 | AC | 139 ms
19,796 KB |
testcase_40 | AC | 56 ms
11,012 KB |
testcase_41 | AC | 59 ms
14,308 KB |
testcase_42 | AC | 76 ms
18,108 KB |
testcase_43 | AC | 95 ms
14,980 KB |
testcase_44 | AC | 100 ms
17,792 KB |
testcase_45 | AC | 106 ms
10,180 KB |
testcase_46 | AC | 131 ms
18,056 KB |
testcase_47 | AC | 47 ms
12,872 KB |
testcase_48 | AC | 71 ms
17,824 KB |
testcase_49 | AC | 67 ms
17,904 KB |
testcase_50 | AC | 34 ms
14,308 KB |
testcase_51 | AC | 134 ms
18,356 KB |
testcase_52 | AC | 98 ms
12,596 KB |
testcase_53 | AC | 51 ms
11,904 KB |
testcase_54 | AC | 97 ms
13,428 KB |
testcase_55 | AC | 32 ms
11,544 KB |
testcase_56 | AC | 27 ms
11,804 KB |
testcase_57 | AC | 46 ms
11,160 KB |
testcase_58 | AC | 100 ms
9,676 KB |
testcase_59 | AC | 24 ms
10,380 KB |
testcase_60 | AC | 65 ms
11,472 KB |
testcase_61 | AC | 35 ms
8,172 KB |
testcase_62 | AC | 75 ms
10,864 KB |
testcase_63 | AC | 63 ms
11,168 KB |
testcase_64 | AC | 23 ms
8,604 KB |
testcase_65 | AC | 53 ms
16,572 KB |
testcase_66 | AC | 46 ms
10,072 KB |
testcase_67 | AC | 78 ms
13,660 KB |
testcase_68 | AC | 83 ms
10,732 KB |
testcase_69 | AC | 49 ms
18,320 KB |
testcase_70 | AC | 29 ms
10,936 KB |
testcase_71 | AC | 34 ms
11,236 KB |
testcase_72 | AC | 65 ms
8,468 KB |
testcase_73 | AC | 46 ms
14,696 KB |
testcase_74 | AC | 98 ms
17,332 KB |
testcase_75 | AC | 48 ms
11,504 KB |
testcase_76 | AC | 81 ms
15,236 KB |
testcase_77 | AC | 84 ms
18,444 KB |
testcase_78 | AC | 100 ms
11,028 KB |
testcase_79 | AC | 97 ms
14,344 KB |
testcase_80 | AC | 87 ms
14,360 KB |
testcase_81 | AC | 66 ms
14,316 KB |
testcase_82 | AC | 212 ms
47,412 KB |
testcase_83 | AC | 282 ms
47,332 KB |
testcase_84 | AC | 2,365 ms
47,392 KB |
testcase_85 | AC | 275 ms
45,284 KB |
testcase_86 | AC | 145 ms
45,388 KB |
testcase_87 | AC | 362 ms
47,652 KB |
testcase_88 | AC | 363 ms
47,476 KB |
testcase_89 | AC | 358 ms
47,344 KB |
testcase_90 | AC | 365 ms
47,512 KB |
testcase_91 | AC | 366 ms
47,332 KB |
testcase_92 | AC | 454 ms
47,380 KB |
testcase_93 | AC | 453 ms
47,392 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; //BEGIN CUT HERE struct Mo{ using F = function<void(Int)>; vector<Int> ls,rs,ord; Int n,width,nl,nr,ptr; vector<bool> flg; F expand,shrink; Mo(Int n,Int width,F expand,F shrink): n(n),width(width),nl(0),nr(0),ptr(0),flg(n,0), expand(expand),shrink(shrink){} void add(Int l,Int r){ ls.emplace_back(l); rs.emplace_back(r); } void build(){ ord.resize(ls.size()); iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(), [&](Int a,Int b){ if(ls[a]/width!=ls[b]/width) return ls[a]<ls[b]; return bool((rs[a]<rs[b])^((ls[a]/width)&1)); }); } Int process(){ if(ptr==(Int)ord.size()) return -1; const Int idx=ord[ptr++]; while(nl>ls[idx]) calc(--nl); while(nr<rs[idx]) calc(nr++); while(nl<ls[idx]) calc(nl++); while(nr>rs[idx]) calc(--nr); return idx; } inline void calc(Int idx){ flg[idx].flip(); if(flg[idx]) expand(idx); else shrink(idx); } }; //END CUT HERE template<typename T> map<T, Int> factorize(T x){ map<T, Int> res; for(Int i=2;i*i<=x;i++){ while(x%i==0){ x/=i; res[i]++; } } if(x!=1) res[x]++; return res; } template<typename T> vector<T> make_v(size_t a){return vector<T>(a);} template<typename T> vector<vector<T> > make_v(size_t a,size_t b){ return vector<vector<T> >(a,make_v<T>(b)); } template<typename T> vector<vector<vector<T> > > make_v(size_t a,size_t b,size_t c){ return vector<vector<vector<T> > > (a,make_v<T>(b,c)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;} template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){ for(auto &e:t) fill_v(e,v); } class EulerTourForEdge{ private: vector<Int> ds,us,dep,btm; void dfs(Int v,Int p,Int d){ dep[v]=d; for(Int u:G[v]){ if(u==p) continue; ds[u]=btm.size(); btm.emplace_back(u); dfs(u,v,d+1); us[u]=btm.size(); btm.emplace_back(u); } } public: vector<vector<Int> > G; EulerTourForEdge(){} EulerTourForEdge(Int n): ds(n),us(n),dep(n),G(n){} void add_edge(Int u,Int v){ G[u].emplace_back(v); G[v].emplace_back(u); } void build(Int r=0){ btm.clear(); ds[r]=btm.size(); btm.emplace_back(r); dfs(r,-1,0); us[r]=btm.size(); btm.emplace_back(r); } Int child(Int u,Int v){ return dep[u]<dep[v]?v:u; } Int bottom(Int e){ return btm[e]; } // lca(u, v) must be u or v template<typename F> void query(Int u,Int v,F f){ if(dep[u]>dep[v]) swap(u,v); f(ds[u]+1,ds[v]+1); } template<typename T,typename G> void update(Int v,T x,G g){ g(ds[v], x); g(us[v],-x); } }; //INSERT ABOVE HERE signed DWANGO2017FINAL_B(){ using ll = long long; Int n; cin>>n; vector<Int> x(n); for(Int i=0;i<n;i++) cin>>x[i]; const Int RT = 40; auto acc=make_v<Int>(RT,n+1); fill_v(acc,0); using P = pair<Int, Int>; vector<vector<P> > v(n); for(Int i=0;i<n;i++){ for(auto p:factorize(x[i])){ if(p.first<RT) acc[p.first][i+1]+=p.second; else v[i].emplace_back(p); } } for(Int j=0;j<RT;j++) for(Int i=0;i<n;i++) acc[j][i+1]+=acc[j][i]; const Int MAX = 5e5+100; vector<Int> cnt(MAX,0); auto expand=[&](Int idx){ for(auto p:v[idx]){ cnt[p.first]+=p.second; } }; auto shrink=[&](Int idx){ for(auto p:v[idx]){ cnt[p.first]-=p.second; } }; Mo mo(n,400,expand,shrink); Int q; cin>>q; vector<Int> ps(q); for(Int i=0;i<q;i++){ Int l,r; cin>>ps[i]>>l>>r; l--; mo.add(l,r); } mo.build(); vector<ll> ans(q,1); for(Int i=0;i<q;i++){ Int k=mo.process(); Int l=mo.ls[k],r=mo.rs[k]; if((acc[0][r]-acc[0][l])>=1){ ans[k]=1; continue; } auto mp=factorize(ps[k]); for(auto p:mp){ if(p.first<RT) ans[k]&=(acc[p.first][r]-acc[p.first][l])>=p.second; else ans[k]&=cnt[p.first]>=p.second; } } for(Int i=0;i<q;i++) cout<<(ans[i]?"Yes":"NO")<<"\n"; cout<<flush; return 0; } /* verified on 2018/02/02 https://beta.atcoder.jp/contests/dwacon2017-honsen/tasks/dwango2017final_b */ signed main(){ DWANGO2017FINAL_B(); //ABC133_F(); return 0; }