結果
問題 | No.854 公平なりんご分配 |
ユーザー | NyaanNyaan |
提出日時 | 2019-07-26 22:50:37 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 9,386 bytes |
コンパイル時間 | 1,623 ms |
コンパイル使用メモリ | 129,076 KB |
実行使用メモリ | 114,432 KB |
最終ジャッジ日時 | 2024-07-02 08:46:28 |
合計ジャッジ時間 | 15,305 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
12,188 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | RE | - |
testcase_33 | RE | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
testcase_36 | RE | - |
testcase_37 | RE | - |
testcase_38 | RE | - |
testcase_39 | RE | - |
testcase_40 | RE | - |
testcase_41 | RE | - |
testcase_42 | RE | - |
testcase_43 | RE | - |
testcase_44 | RE | - |
testcase_45 | RE | - |
testcase_46 | RE | - |
testcase_47 | RE | - |
testcase_48 | RE | - |
testcase_49 | RE | - |
testcase_50 | RE | - |
testcase_51 | RE | - |
testcase_52 | TLE | - |
testcase_53 | -- | - |
testcase_54 | -- | - |
testcase_55 | -- | - |
testcase_56 | -- | - |
testcase_57 | -- | - |
testcase_58 | -- | - |
testcase_59 | -- | - |
testcase_60 | -- | - |
testcase_61 | -- | - |
testcase_62 | -- | - |
testcase_63 | -- | - |
testcase_64 | -- | - |
testcase_65 | -- | - |
testcase_66 | -- | - |
testcase_67 | -- | - |
testcase_68 | -- | - |
testcase_69 | -- | - |
testcase_70 | -- | - |
testcase_71 | -- | - |
testcase_72 | -- | - |
testcase_73 | -- | - |
testcase_74 | -- | - |
testcase_75 | -- | - |
testcase_76 | -- | - |
testcase_77 | -- | - |
testcase_78 | -- | - |
testcase_79 | -- | - |
testcase_80 | -- | - |
testcase_81 | -- | - |
testcase_82 | -- | - |
testcase_83 | -- | - |
testcase_84 | -- | - |
testcase_85 | -- | - |
testcase_86 | -- | - |
testcase_87 | -- | - |
testcase_88 | -- | - |
testcase_89 | -- | - |
testcase_90 | -- | - |
testcase_91 | -- | - |
testcase_92 | -- | - |
testcase_93 | -- | - |
ソースコード
#pragma GCC optimize("O2") #include <algorithm> #include <bitset> #include <cassert> #include <cmath> #include <cstdarg> #include <cstdio> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <iterator> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <utility> #include <vector> #define whlie while #define retunr return #define reutrn return #define reutnr return #define mp make_pair #define pb push_back #define eb emplace_back #define fi first #define se second #define inf 1001001001 #define MOD 998244353 #define infLL (1LL << 61) #define FOR(i,a,b) for(int (i)=(int)(a); (i)<(int)(b); (i)++) // [a,b) #define rep(i,N) FOR((i), 0, (int)(N)) // [0,N) #define FORR(i,a,b) for(int (i)=(int)(b) - 1; (i)>=(int)(a); (i)--) #define repr(i,N) FORR((i), 0, (int)(N)) #define each(x,v) for(auto &x : v) #define all(v) (v).begin(),(v).end() #define sz(v) ((int)(v).size()) #define vrep(v,it) for(auto it=v.begin();it!=v.end();it++) #define vrepr(v,it) for(auto it=v.rbegin();it!=v.rend();it++) #define ini(...) int __VA_ARGS__; in(__VA_ARGS__) #define inl(...) ll __VA_ARGS__; in(__VA_ARGS__) #define inc(...) char __VA_ARGS__; in(__VA_ARGS__) #define ins(...) string __VA_ARGS__; in(__VA_ARGS__) #define ind(...) double __VA_ARGS__; in(__VA_ARGS__) #define inpii(...) pii __VA_ARGS__; in(__VA_ARGS__) //#define rand mtrand //#define randinit random_device seed_gen; mt19937_64 mtrand(seed_gen()) #ifdef LOCAL #define trc(...) do { cout << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0) #define stopif(val) assert( !(val) ) #define trcv(v,...) do { cout << #v << " = "; vector_debug(v , ##__VA_ARGS__);cout << endl;} while(0) #else #define trc(...) #define stopif(...) #define trcv(...) #endif using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; using vi = vector<int>; using vl = vector<ll>; using vs = vector<string>; using vpii = vector<pii>; using vvi = vector< vector<int> >; struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(15);} } iosetupnya; /* int gcd(int a, int b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);} ll gcd(ll a, ll b){if(a>b) swap(a,b); return a==0 ? b : gcd(b%a,a);} ll lcm(int a, int b){return (1LL * a / gcd(a,b)) * b;} ll lcm(ll a, ll b){return (a / gcd(a,b)) * b;} */ inline ll pow(int a, int b){ll ans = 1; rep(i,b) ans *= a; return ans;} inline ll pow(ll a, ll b){ll ans = 1; rep(i,b) ans*= a; return ans;} inline ll pow(int a, ll b){ll ans = 1; rep(i,b) ans *= a; return ans;} inline ll pow(ll a, int b){ll ans = 1; rep(i,b) ans*= a; return ans;} template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template<typename C> inline void _cin(C &c){cin >> c;} template<typename T,typename U> inline void _cin(pair<T,U> &p){cin >> p.fi; cin >> p.se;} template<typename C> inline void _cout(const C &c){cout << c;} template<typename T,typename U> inline void _cout(const pair<T,U> &p){cout << p.fi << ' ' << p.se;} void in(){} template <typename T,class... U> void in(T &t,U &...u){ _cin(t); in(u...);} void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ' '; out(u...);} template<typename C> inline void in(vector<C> &v,int N=-1){if(sz(v) != 0){int M=(N == -1) ? sz(v) : N; rep(i,M) _cin(v[i]);}else{C c;rep(i,N) v.pb((_cin(c),c));}} template<typename C> inline void in(C v[],int N){rep(i,N) _cin(v[i]);} template<typename C> inline void out(const vector<C> &v,int N=-1){int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<"\n";} template<typename C> inline void out(C v[],int N){rep(i,N) {cout<<( (i)?" ":"" ); _cout(v[i]);} cout<<"\n";} template<typename C> inline void vector_debug(const vector<C> &v,int N=-1){cout << "{"; int M=(N == -1) ? sz(v) : N; rep(i,M) {cout<<( (i)?", ":"" ); _cout(v[i]);} cout<<"}";} template<typename C> inline void vector_debug(C v[], int N){cout << "{"; rep(i,N) {cout<<((i)?", ":""); _cout(*(v+i));} cout<<"}";} void dbg_out(){cout << endl;} template <typename T,class... U> void dbg_out(const T &t,U ...u){ _cout(t); if(sizeof...(u)) cout << ", "; dbg_out(u...);} template<typename C,class... U> void dbg_out(const vector<C> &v,U ...u){vector_debug(v); if(sizeof...(u)) cout << ", "; dbg_out(u...);} template<typename C,class... U> void dbg_out(const vector<vector<C>> &v,U ...u){cout << "{ "; rep(i,sz(v)) {if(i)cout<<", "; vector_debug(v[i]);} cout << " }"; if(sizeof...(u)) cout << ", "; dbg_out(u...);} template<typename C> inline C vmax(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amax(n,v[i]); return n;} template<typename C> inline C vmax(C v[], int N){C n=v[0]; rep( i , N ) amax(n,v[i]); return n;} template<typename C> inline C vmin(const vector<C> &v){C n=v[0]; rep(i,sz(v)) amin(n,v[i]); return n;} template<typename C> inline C vmin(C v[], int N){C n=v[0]; rep( i , N ) amin(n,v[i]); return n;} void die(string s){out(s); exit(0);} //////////// /// main /// //////////// // 1からNまでの素数を判定するライブラリ // A[i] == 1 <-> iは素数 void prime(vi& A,int N){ rep(i,N + 1) A[i] = 1; A[0] = 0; A[1] = 0; for(int i=2 ; i*i <= N ; i++){ if(A[i]){ for(int j=2; i*j <= N; j++){ A[i*j] = 0; } } } } // 省メモリセグ木 使いどころある? ないですね(完) template<typename T,typename F,T UNIT> struct ST{ int size; vector<T> seg; F func; vector<int> seg_sz; ST(){}; ST(const vector<T> &v,F func) : func(func){ // initialize seg.resize( ( size = v.size() ) << 1 , UNIT); // set // n A[n]まで見た int n = 0; seg_sz.pb(0); while(n < size){ // これからm個の配列を埋める int m = 1 << (31 - __builtin_clz(size ^ n) ); for(int i = n; i < n + m; i++){ //trc(n , m , i); seg[n + m + i] = v[i]; } seg_sz.pb( (n += m) ); } // build(); } void build(){ vector<int>::const_iterator it = seg_sz.begin(); while(1){ int l = *(it++); if(it == seg_sz.end()) return; int r = *it; const int dif = l << 1; // k 添え字のズレ for( int i = r - l - 1; i > 0; i-- ){ seg[dif | i] = func(seg[dif | (i << 1)] , seg[dif | (i << 1) | 1]); } } } void update(int k, T& x){ vector<int>::const_iterator it = upper_bound(seg_sz.begin() , seg_sz.end() , k); seg[ (k += *it) ] = x; it--; k -= (*it) << 1; const int dif = (*it) << 1; //trc(k , dif); // [*it , *(it + 1) ) 間のセグ木を更新 添え字はdifずれている while(k >>= 1){ seg[dif | k] = func(seg[dif | (k << 1)] , seg[dif | (k << 1) | 1]); } } // [a,b)へのクエリ T query(int a, int b){ //trc("query" , a , b); if(a < 0){a = 0;} b--; // いったん閉区間にする // おなじセグ木に乗せる処理 T ret = UNIT; vector<int>::const_iterator itl = upper_bound(seg_sz.begin() , seg_sz.end() , a), itr = upper_bound(seg_sz.begin() , seg_sz.end() , b); itl--; const int cur_sz = *(itr--) - *itr;// 右側の載っているセグ木のサイズ //trc(ret , *itl , *itr); while(itl != itr) { if(a == *itl) ret = func(ret , seg[ ( (*itl++) << 1 ) | 1 ]); else ret = func(ret , query(a , (*(++itl))) ); a = *itl; //trc(ret , *itl , *itr); } const int dif = (*itr) << 1; // 普通のセグ木の処理 セグ木のサイズはcur_sz a,bは添え字はdifずれる T L = UNIT, R = UNIT; for( a += cur_sz - *itr , b += cur_sz + 1 - *itr ; a<b; a>>=1,b>>=1){ if(a & 1) L = func(L,seg[dif | (a++)]); if(b & 1) R = func(seg[dif | (--b)],R); } return func(ret , func(L, R) ); } T operator[](const int &k) const{ vector<int>::const_iterator it = upper_bound(seg_sz.begin() , seg_sz.end() , k); return seg[ *it + k ]; } }; auto f = [](int a,int b){return a + b;}; int main(){ ini(N); vi a(N); in(a,N); ini(Q); vi P(Q),L(Q),R(Q); rep(i,Q) in(P[i],L[i],R[i]); vi A(2001); prime(A , 2000); vi lst; lst.reserve(1000); int nyanya = 0; rep(i,2001) if(A[i] == 1) { A[i] = nyanya++; lst.pb(i); } trc(sz(lst)); vvi data(303 , vi(N , 0)); rep(i,N){ rep(j,303){ while(a[i] % lst[j] == 0){ data[j][i]++; a[i] /= lst[j]; } } } //out("hoe"); vector< ST<int , decltype(f) , 0> > st; st.reserve(303); rep(i,303){ st.pb(ST<int , decltype(f) , 0>(data[i] , f)); } rep(i,Q){ int flg = 1; for(int nya=2;nya*nya<=P[i];nya++){ if(P[i] % nya == 0){ int cur = st[A[nya]].query(L[i]-1,R[i]); trc(nya , cur); while(P[i] % nya == 0){ if(cur == 0) {flg = 0; break;} P[i] /= nya; cur--; } } if(flg == 0) break; } trc(P[i]); if(P[i] != 1){ int nyaa = P[i]; int curr = st[A[nyaa]].query(L[i]-1,R[i]); if(curr == 0) flg = 0; } out(flg ? "Yes" : "NO"); } }