//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 500005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> pos[maxn], del[maxn];
int rig[maxn], lef[maxn];
int c[maxn];
bool done[maxn];
pii ans[maxn];
int main() {
io
int n;
cin >> n;
for (int i = 1;i <= n - 1;i++) cin >> c[i];
for (int i = 1;i <= n;i++) pos[i].push_back(-1);
for (int i = 1;i <= n;i++) {
lef[i] = -1;
rig[i] = n+2;
ans[i] = {1, n};
int bi;
cin >> bi;
for (int j = 0;j < bi;j++) {
int x;cin>> x;
pos[x].push_back(i);
}
}
for (int i = 1;i <= n;i++) pos[i].push_back(n+2);
for (int i = 1;i <= n-1;i++) {
int ri = *lower_bound(pos[c[i]].begin(), pos[c[i]].end(), i+1);
lef[i] = max(lef[i], ri);
int li = *prev(upper_bound(pos[c[i]].begin(), pos[c[i]].end(), i));
rig[i+1] = min(rig[i+1], li);
}
lef[0] = n+2, lef[n+1] = -1;
rig[n+1] = -1, rig[0] = n+2;
//debug();
//pary(rig, rig + n + 1);
multiset<int> se;
se.insert(n+1);
auto upd = [&] (int l, int r) {
for (int j = l;j <= r;j++) {
if (l > ans[j].ff || (l == ans[j].ff && r < ans[j].ss)) {
ans[j] = {l, r};
}
}
};
for (int i = n;i >= 0;i--) {
for (int j:del[i]) {
if (!done[j]) {
if (j == lef[i]) {
upd(i+1, j-1);
}
se.erase(se.find(j));
}
}
if (lef[i] >= i) {
//debug("lef", i, lef[i]);
int f = 0;
auto it = se.begin();
while (se.size()&& it != se.end()) {
int mi = *it;
if (mi >= lef[i]) break;
//if (f) done[mi] = 1;
upd(i+1, mi-1);
it = next(it);
//if (f) se.erase(se.begin());
//else f = 1;
}
}
if (rig[i] < i) {
se.insert(i);
if (rig[i] >= 0) del[rig[i]].push_back(i);
}
}
for (int i = 1;i <= n;i++) debug(i, ans[i].ff, ans[i].ss);
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
cout << (y <= ans[x].ss && y >= ans[x].ff ? "YES" : "NO") << "\n";
}
}
Compilation message
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:76:8: warning: unused variable 'f' [-Wunused-variable]
76 | int f = 0;
| ^
long_mansion.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
long_mansion.cpp:93:29: note: in expansion of macro 'debug'
93 | for (int i = 1;i <= n;i++) debug(i, ans[i].ff, ans[i].ss);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
34500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
