#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1;
int r = bm(b, p/2);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int f[MAXN];
int nCr(int n, int r) {
int ans = f[n]; ans *= inv(f[r]); ans %= MOD;
ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() {
f[0] = 1;
for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD;
}
void solve(int tc) {
int n;
cin >> n;
int c[n];
vector<int> sad[n + 1];
for(int i=1; i<=n; i++) sad[i].push_back(0);
for(int i=1; i<n; i++) {
cin >> c[i];
sad[c[i]].push_back(i);
}
for(int i=1; i<=n; i++) sad[i].push_back(n);
vector<int> wow[n + 1];
for(int i=1; i<=n; i++) {
int x; cin >> x;
for(int j=0; j<x; j++) {
int y; cin >> y;
wow[y].push_back(i);
}
}
/*
for(int i=1; i<=n; i++) {
cout << "wow[" << i << "] = [";
for(int j=0; j<wow[i].size(); j++) {
cout << wow[i][j] << ",]"[j == wow[i].size() - 1];
if(wow[i].size() - 1 != j) cout << " ";
}
if(wow[i].empty()) cout << "]";
cout << "\n";
}
*/
int l[n+1], r[n+1];
for(int i=1; i<=n; i++) l[i] = 1, r[i] = n;
for(int i=1; i<=n; i++) {
//cout << "i = " << i << ", sad[" << i << "].size = " << sad[i].size() << "\n";
for(int j=1; j<sad[i].size(); j++) {
// if nothing in [range]
int lwb;
if(wow[i].empty()) lwb = MOD;
else if(wow[i][wow[i].size() - 1] < sad[i][j-1] + 1) lwb = MOD;
else lwb = *lower_bound(wow[i].begin(), wow[i].end(), sad[i][j-1] + 1);
//cout << "lower_bound(wow[" << i << "], " << sad[i][j-1] + 1 << ") = " << lwb << "\n";
if(lwb > sad[i][j]) {
// update range
//cout << "range update " << sad[i][j-1] +1 << ' ' << sad[i][j] <<"\n";
for(int k=sad[i][j-1] + 1; k <= sad[i][j]; k++) l[k] = max(l[k], sad[i][j-1] + 1);
for(int k=sad[i][j-1] + 1; k <= sad[i][j]; k++) r[k] = min(r[k], sad[i][j]);
}
}
}
int q;
cin >> q;
while(q--) {
int x, y;
cin >> x >> y;
cout << (l[x] <= y && y <= r[x] ? "YES\n" : "NO\n");
}
}
int32_t main(){
precomp();
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
Compilation message
long_mansion.cpp: In function 'void solve(long long int)':
long_mansion.cpp:64:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j=1; j<sad[i].size(); j++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
2260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
2260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3070 ms |
19196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
2260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
