QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #62530 | #4596. Ironforge | qinjianbin | TL | 0ms | 0kb | C++ | 2.0kb | 2022-11-19 23:22:23 | 2022-11-19 23:22:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, a[N], b[N];
int minv[N];
int L[N], R[N];
vector<int> pos[N];
bool check(int p, int l, int r)
{
if (!pos[p].size() || pos[p].back() < l) return 0;
int x = *lower_bound(pos[p].begin(), pos[p].end(), l);
return (x <= r);
}
void solve()
{
cin >> n >> m;
for(int i = 1 ; i < N ; i ++ ) pos[i].clear();
for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
for(int i = 1 ; i < n ; i ++ ) cin >> b[i];
for(int i = 1 ; i <= n ; i ++ )
{
int x = a[i];
for(int j = 2 ; j * j <= x ; j ++ )
{
if(x % j == 0)
{
while(x % j == 0) x /= j;
pos[j].push_back(i);
}
}
if(x > 1) pos[x].push_back(i);
}
for(int i = n ; i ; i -- )
{
R[i] = i;
while(R[i] < n && check(b[R[i]], i, R[i]))
R[i] = R[R[i] + 1];
}
for(int i = 1 ; i <= n ; i ++ )
{
if(i > 1 && R[i - 1] >= i)
{
if(check(b[i - 1], i, R[i]))
{
L[i] = L[i - 1];
R[i] = R[i - 1];
}
else L[i] = i;
}
else
{
while(1)
{
bool flag = false;
while(L[i] > 1 && check(b[L[i] - 1], L[i], R[i]))
{
flag = true;
L[i] = L[L[i] - 1];
}
while(R[i] < n && check(b[R[i]], L[i], R[i]))
{
flag = true;
R[i] = R[R[i] + 1];
}
if(!flag) break;
}
}
}
for(int i = 1 ; i <= m ; i ++ )
{
int a, b;
cin >> a >> b;
if(L[a] <= b && R[a] >= b) puts("Yes");
else puts("No");
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
int T = 1;
cin >> T;
while(T -- ) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
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 Yes Yes Yes Yes Yes No No No Yes No Yes No Yes No No Yes No Yes Yes Yes Yes No No Yes Yes Yes Yes Yes No No Yes No Yes Yes Yes No No Yes No No Yes Yes Yes Yes No Yes Yes Yes Yes No Yes No Yes Yes Yes Yes Yes Yes No Yes No Yes Yes Yes Y...