QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #62519 | #4596. Ironforge | qinjianbin | WA | 454ms | 46588kb | C++ | 2.7kb | 2022-11-19 22:47:01 | 2022-11-19 22:47:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int pr[MAXN], p_sz;
bool vis[MAXN];
void init() {
for (int i = 2; i < MAXN; i++) {
if (!vis[i]) pr[p_sz++] = i;
for (int j = 0; j < p_sz; j++) {
if (pr[j] * i >= MAXN) break;
vis[pr[j] * i] = 1;
if (i % pr[j] == 0) break;
}
}
}
void change(int num, set<int>& st) {
int t = sqrt(num + 0.5);
for (int i = 0; pr[i] <= t; i++) {
if (num % pr[i] == 0) {
st.insert(pr[i]);
while (num % pr[i] == 0) num /= pr[i];
}
}
if (num > 1) st.insert(num);
}
int T, n, m;
struct Node {
int l, r;
int ll, rr;
set<int> st;
void init() {
st.clear();
}
}a[MAXN];
struct BNode {
int num;
int l, r;
}b[MAXN];
map<int, int> mp;
void fun() { //update a[].l, a[].r
for (int i = n; i >= 1; i--) {
int ind = i;
while (ind < n && b[ind].l >= i) { //需要的在起点的右边
ind = a[ind + 1].r;
}
a[i].r = ind;
}
for (int i = 1; i <= n; i++) {
int ind = i;
while (ind - 1 > 0 && b[ind - 1].r <= i) {
ind = a[ind - 1].l;
}
a[i].l = ind;
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) a[i].init();
int tmp;
for (int i = 1; i <= n; i++) {
scanf("%d", &tmp);
change(tmp, a[i].st);
}
for (int i = 1; i < n; i++)
scanf("%d", &b[i].num);
mp.clear();
for (int i = 1; i <= n; i++) {
for (auto it : a[i].st)
mp[it] = i;
if (i != n) {
if (mp.count(b[i].num)) b[i].l = mp[b[i].num];
else b[i].l = 0;
}
}
mp.clear();
for (int i = n; i >= 1; i--) {
for (auto it : a[i].st)
mp[it] = i;
if (i != 1) {
if (mp.count(b[i - 1].num)) b[i - 1].r = mp[b[i - 1].num];
else b[i - 1].r = n + 1;
}
}
fun();
a[1].ll = a[1].l, a[1].rr = a[1].r;
for (int i = 2; i <= n; i++) {
if (a[i - 1].rr >= i && a[i].l <= i - 1) {
a[i].ll = a[i - 1].ll;
a[i].rr = a[i - 1].rr;
}
else {
int indl = a[i - 1].ll;
if (a[i].l >= i) indl = a[i].l;
int indr = a[i].r;
while (1) {
bool flag = false;
while (indr < n && b[indr].l >= indl) {
indr = a[indr + 1].r;
flag = true;
}
while (indl - 1 > 0 && b[indl - 1].r <= indr) {
indl = a[indl - 1].ll;
indr = max(indr, a[indl - 1].rr);
flag = true;
}
if (!flag) break;
}
a[i].ll = indl;
a[i].rr = indr;
}
}
int x, y;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
if (y >= a[x].ll && y <= a[x].rr) puts("Yes");
else puts("No");
}
}
int main() {
init();
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 454ms
memory: 46588kb
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 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 Yes Yes Yes No Yes No Yes Yes No Yes Yes No No No No Yes Yes No Yes No Yes ...
result:
wrong answer 20th lines differ - expected: 'No', found: 'Yes'