/* cerberus97 - Hanit Banga */
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 5e5 + 10, LOG = log2(N) + 5;
int c[N], lkey[N], rkey[N], lg2[N];
int lmost[N], lmost_table[N][LOG];
int rmost[N], rmost_table[N][LOG];
vector<int> pos[N];
void build_table(int *a, int table[N][LOG], int n, int f(int, int));
int query(int table[N][LOG], int l, int r, int f(int, int));
int my_min(int x, int y);
int my_max(int x, int y);
int main() {
fast_cin();
int n; cin >> n;
for (int i = 1; i <= n - 1; ++i) {
cin >> c[i];
}
for (int i = 1; i <= n; ++i) {
int b; cin >> b;
for (int j = 0; j < b; ++j) {
int k; cin >> k;
pos[k].pb(i);
}
}
for (int i = 1; i <= n; ++i) {
pos[i].pb(0);
pos[i].pb(n + 1);
sort(pos[i].begin(), pos[i].end());
}
for (int i = 1; i <= n - 1; ++i) {
auto it = lower_bound(pos[c[i]].begin(), pos[c[i]].end(), i + 1);
rkey[i] = *it;
lkey[i] = *(it - 1);
}
rkey[0] = n + 1;
lkey[n] = 0;
set<pii> s;
for (int i = 1; i <= n - 1; ++i) {
s.insert({i - 1, rkey[i - 1]});
int p = lkey[i];
lmost[i] = i;
while (true) {
auto it = s.lower_bound({p, 0});
if (it == s.end()) {
break;
} else if (it->second < i + 1) {
s.erase(it);
} else {
lmost[i] = it->first;
break;
}
}
}
s.clear();
for (int i = n - 1; i >= 1; --i) {
s.insert({i + 1, lkey[i + 1]});
int p = rkey[i];
rmost[i] = i;
while (true) {
auto it = s.lower_bound({p, 0});
if (it == s.begin()) {
break;
}
--it;
if (it->second > i) {
s.erase(it);
} else {
rmost[i] = it->first;
break;
}
}
}
for (int i = 1; i <= n; ++i) {
lg2[i] = lg2[i - 1];
while (1 << (lg2[i] + 1) <= i) {
++lg2[i];
}
}
build_table(lmost, lmost_table, n - 1, my_min);
build_table(rmost, rmost_table, n - 1, my_max);
int q; cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
if (x < y) {
if (query(lmost_table, x, y - 1, my_min) < x) {
cout << "NO\n";
} else {
cout << "YES\n";
}
} else {
if (query(rmost_table, y, x - 1, my_max) > x) {
cout << "NO\n";
} else {
cout << "YES\n";
}
}
}
}
void build_table(int *a, int table[N][LOG], int n, int f(int, int)) {
for (int i = n; i >= 1; --i) {
table[i][0] = a[i];
for (int j = 1; i + (1 << j) - 1 <= n; ++j) {
table[i][j] = f(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int table[N][LOG], int l, int r, int f(int, int)) {
int j = lg2[r - l + 1];
return f(table[l][j], table[r - (1 << j) + 1][j]);
}
int my_min(int x, int y) {
return min(x, y);
}
int my_max(int x, int y) {
return max(x, y);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
332 ms |
41220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
