QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #62368 | #4596. Ironforge | qinjianbin# | WA | 513ms | 46772kb | C++17 | 3.2kb | 2022-11-18 15:37:07 | 2022-11-18 15:37:08 |
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;
Node (int l = 0, int r = 0, int ll = 0, int rr = 0) : l(l), r(r), ll(ll), rr(rr) {}
void init() {
st.clear();
l = r = ll = rr = 0;
}
}a[MAXN];
struct BNode {
int num;
int l, r;
void init() {
l = r = 0;
}
}b[MAXN];
map<int, int> mp;
void fun(bool flag) { //update a[].l, a[].r
if (!flag) {
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;
}
}
else {
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(), b[i].init();
int tmp;
for (int i = 1; i <= n; i++) {
scanf("%d", &tmp);
change(tmp, a[i].st);
a[i].l = a[i].r = a[i].ll = a[i].rr = i;
// printf("qweqwr ");
// for (auto it: a[i].st)
// printf("%d ", it);
// puts("");
}
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;
}
}
// for (int i = 1; i < n; i++)
// printf("%d %d\n", b[i].l, b[i].r);
fun(0); fun(1);
a[1].ll = a[1].l, a[1].rr = a[1].r;
for (int i = 2; i <= n; i++) {
if (a[i - 1].r >= i && a[i].l <= i - 1) {
a[i].ll = a[i - 1].ll;
a[i].rr = a[i - 1].rr;
}
else {
int indr = a[i].r;
int indl = a[i - 1].ll;
if (a[i].l >= i) {
indl = a[i].l;
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;
// printf("dadfad ");
// for (int i = 1; i <= n ;i++)
// printf("%d %d\n", a[i].ll, a[i].rr);
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;
}
/*
1
5 3
10 14 6 1 5
2 3 5 7
3 5
4 5
1 3
*/
详细
Test #1:
score: 0
Wrong Answer
time: 513ms
memory: 46772kb
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'