結果
問題 | No.854 公平なりんご分配 |
ユーザー |
👑 ![]() |
提出日時 | 2019-07-26 23:08:51 |
言語 | C++11 (gcc 13.3.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,761 bytes |
コンパイル時間 | 2,156 ms |
コンパイル使用メモリ | 176,940 KB |
実行使用メモリ | 818,576 KB |
最終ジャッジ日時 | 2024-07-02 09:18:14 |
合計ジャッジ時間 | 53,512 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 67 MLE * 14 -- * 11 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(a) (a).begin(),(a).end() #define ALLR(a) (a).rbegin(),(a).rend() #define spa << " " << #define test cout<<"test"<<endl; #define fi first #define se second #define rep(i,n,m) for(ll i = n; i < (ll)(m); i++) #define rrep(i,n,m) for(ll i = n; i < (ll)(m); i--) typedef int ll; typedef long double ld; const ll MOD = 1e9+7; //const ll MOD = 998244353; //const ll INF = 1e18; using P = pair<ll, ll>; void chmin(ll &a,ll b){if(a>b)a=b;} void chmax(ll &a,ll b){if(a<b)a=b;} void pmod(ll &a,ll b){a=(a+b)%MOD;} void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;} void qmod(ll &a,ll b){a=(a*b)%MOD;} void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;} ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});} void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;} void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;} void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;} void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;} void ans(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;} void debug(vector<vector<ll>>v,ll h,ll w){for(ll i=0;i<h;i++) {cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}}; void debug(vector<string>v,ll h,ll w){for(ll i=0;i<h;i++) {for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}}; void debug(vector<ll>v,ll n){cout<<v[0]; for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;}; ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;} //m.emplace(x,0).fi->second++; map<ll,ll> factoring(ll n){ ll buf=n; map<ll,ll>ret; ll i,j; for(i=2;buf!=1&&i*i<=n;i++){ for(j=0;buf%i==0;j++){ buf/=i; } if(j>0)ret.emplace(i,j); } if(buf!=1)ret.emplace(buf,1); return ret; } int main(){ ll res=0,buf=0; bool judge = true; ll n;cin>>n; vector<ll>a(n); vector<ll>b(n+1); rep(i,0,n){ cin>>a[i]; if(a[i]==0)b[i+1]=b[i]+1; else b[i+1]=b[i]; } ll q;cin>>q; vector<ll>p(q),l(q),r(q); rep(i,0,q)cin>>p[i]>>l[i]>>r[i]; vector<map<ll,ll>>v(n+1); rep(i,2,2001){ judge=true; rep(j,2,i-1)if(i%j==0)judge=false; if(judge)v[0].emplace(i,0); } rep(i,0,n){ auto m=factoring(a[i]); for(auto z:v[i]){ if(m.find(z.fi)!=m.end()){ v[i+1].emplace(z.fi,z.se+m[z.fi]); } else v[i+1].emplace(z.fi,z.se); } } rep(i,0,q){ auto m=factoring(p[i]); judge=true; for(auto z:m){ //cout<<z.fi spa z.se<<endl; if(v[l[i]-1].find(z.fi)==v[l[i]-1].end()){ judge=false;break; } else{ if(v[r[i]][z.fi]-v[l[i]-1][z.fi]<z.se){ judge=false;break; } } } if(b[l[i]-1]!=b[r[i]])judge=true; if(judge)cout<<"Yes"<<endl; else cout<<"NO"<<endl; } return 0; }