QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #44319 | #4596. Ironforge | Gemini7X | AC ✓ | 304ms | 26768kb | C++20 | 2.2kb | 2022-08-15 15:55:15 | 2022-08-15 15:55:16 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=2e5+5;
template<typename T>
void read(T &x){
T sgn=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')sgn=-1;
for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
x*=sgn;
}
int n,m;
int a[maxn],b[maxn];
int prime[maxn],cnt;
bool mark[maxn];
vector<int> fac[maxn],vec[maxn];
int L[maxn],R[maxn],MAX=200000;
void sieve(int mx){
for(int i=2;i<=mx;i++){
if(!mark[i]){
prime[++cnt]=i;
}
for(int j=1;j<=cnt&&prime[j]*i<=mx;j++){
mark[i*prime[j]]=true;
if(i%prime[j]==0)break;
}
}
for(int i=1;i<=cnt;i++){
for(int j=prime[i];j<=mx;j+=prime[i]){
fac[j].pb(prime[i]);
}
}
}
bool check(int l,int r,int p){
if(vec[p].size()==0)return false;
int x=lower_bound(vec[p].begin(),vec[p].end(),l)-vec[p].begin();
if(x<vec[p].size()&&vec[p][x]<=r)return true;
return false;
}
void MAIN(){
read(n);read(m);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1;i<n;i++)read(b[i]);
for(int i=1;i<=MAX;i++)vec[i].clear();
for(int i=1;i<=n;i++)
for(int j:fac[a[i]])
vec[j].pb(i);
for(int i=n;i;i--){
R[i]=i;
while(R[i]<n&&check(i,R[i],b[R[i]])){
R[i]=R[R[i]+1];
}
}
L[1]=1;
for(int i=2;i<=n;i++){
if(R[i-1]>=i){
if(check(i,R[i],b[i-1])){
L[i]=L[i-1];
R[i]=R[i-1];
}else{
L[i]=i;
}
}else{
L[i]=i;
while(1){
bool ok=false;
while(R[i]<n&&check(L[i],R[i],b[R[i]])){
R[i]=R[R[i]+1];
ok=true;
}
while(L[i]>1&&check(L[i],R[i],b[L[i]-1])){
L[i]=L[L[i]-1];
ok=true;
}
if(!ok)break;
}
}
}
while(m--){
int x,y;
read(x);read(y);
puts(L[x]<=y&&y<=R[x]?"Yes":"No");
}
}
int main(){
sieve(MAX);
int T;read(T);while(T--)MAIN();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 304ms
memory: 26768kb
input:
3 199997 200000 4147 247 11 1 19 1 11 11 13 19 377 377 4147 319 19 11 13 29 13 1 19 13 11 6061 13 143 551 4147 247 13 29 6061 13 319 377 2717 29 11 247 319 551 247 29 19 551 11 13 377 29 377 19 1 2717 247 1 29 11 1 19 143 29 11 377 143 4147 2717 4147 247 7163 1 209 551 13 1 1 551 13 143 209 143 13 1...
output:
No No No No Yes Yes Yes Yes No Yes No Yes Yes No No No Yes No No No No Yes Yes Yes No No No Yes No Yes No Yes No No Yes No Yes Yes Yes Yes No No Yes Yes Yes No Yes No No Yes No Yes Yes No No No Yes No No No No Yes No No Yes No Yes Yes No Yes No Yes Yes No Yes Yes No No No No Yes Yes No Yes No Yes No...
result:
ok 599998 lines