#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1, MOD = 998244353;
typedef long long ll;
int n,q,c[N],b[N];
vector<array<int,3>> res(N);
vector<int> a[N];
int used[N],timer = 0,mind[N];
unordered_map<int,int> is[N];
vector<pair<int,int>> all;
void go(int l,int r){
if(l >= r) return;
int mid = (l + r) >> 1;
go(l,mid);
go(mid + 1,r);
timer++;
int it = mid;
for(int j:a[it]){
used[j] = timer;
}
for(int i = mid + 1;i <= r;i++){
for(int j:a[i]){
used[j] = timer;
}
while(it >= l && used[c[it - 1]] == timer){
it--;
for(int j:a[it]){
used[j] = timer;
}
}
if(used[c[i]] == timer) continue;
if(it >= l){
all.push_back({it,i});
}
}
timer++;
it = mid + 1;
for(int j:a[it]){
used[j] = timer;
}
for(int i = mid;i >= l;i--){
for(int j:a[i]){
used[j] = timer;
}
while(it <= r && used[c[it]] == timer){
it++;
for(int j:a[it]){
used[j] = timer;
}
}
if(used[c[i - 1]] == timer) continue;
if(it <= r){
all.push_back({it,i});
}
}
}
void test(){
cin >> n;
for(int i = 1;i <= n - 1;i++){
cin >> c[i];
}
for(int i = 1;i <= n;i++){
mind[i] = 1e9;
cin >> b[i];
for(int j = 1;j <=b[i];j++){
int x;
cin >> x;
is[i][x] = 1;
a[i].push_back(x);
}
if(!is[i].count(c[i]) && !is[i].count(c[i - 1])){
mind[i] = 1;
array<int,3> f;
f = {1,i,i};
res[i] = f;
all.push_back({i,i});
}
}
all.push_back({1,n});
go(1,n);
for(int i = 1;i <=n;i++){
// cout << res[i][0] << ' ' << res[i][1] << ' ' << res[i][2] << '\n';
}
int q;
cin >> q;
while(q--){
int x,y;
cin >> x >> y;
int d = 1e9,l,r;
for(auto [X,Y]:all){
if(x > Y || x < X) continue;
if(Y - X + 1 < d){
d = Y - X + 1;
l = X;
r = Y;
}
}
cout << (y >= l && y <= r ? "YES\n":"NO\n");
}
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1; // cin >> T;
while (T--)
test();
}
Compilation message
long_mansion.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
102 | main()
| ^~~~
long_mansion.cpp: In function 'void test()':
long_mansion.cpp:99:25: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | cout << (y >= l && y <= r ? "YES\n":"NO\n");
| ~~~~~~~^~~~~~~~~
long_mansion.cpp:99:51: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
99 | cout << (y >= l && y <= r ? "YES\n":"NO\n");
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
50780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
50780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3022 ms |
82116 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
50780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
