#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#define pii pair<int, int>
#define fst first
#define snd second
#define vi vector<int>
using namespace std;
/*
Idea :
We can transform this problem into a graph traversal problem
Node is defined as (L, R) which is the range currently accessible
The edges have a special property, which can be exploited,
such that we can maintain a data structure where we can query the rightmost cell reachable from a node.
Once we determine the rightmost reachable cell, we can determine the leftmost reachable cell.
*/
int n, q;
int val[500001], goL[500001], goR[500001];
vi pos[500001];
int L[500001], R[500001];
set<pii> s1, s2;
priority_queue<pii> pq;
inline void ins(int x)
{
pii lel = {x, x};
if (s1.size() && prev(s1.end()) -> snd) {lel.fst = prev(s1.end()) -> fst; s1.erase(prev(s1.end()));}
s1.insert(lel);
}
inline void del(int x)
{
auto it = s1.upper_bound({x + 1, -1});
if (it != s1.begin())
{
pii lel = *prev(it); s1.erase(prev(it));
if (lel.fst < x) {s1.insert({lel.fst, x - 1});}
if (x < lel.snd) {s1.insert({x + 1, lel.snd});}
}
}
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n - 1; i++) {cin >> val[i];}
for (int i = 0; i < n; i++)
{
int x; cin >> x;
for (int j = 0; j < x; j++)
{
int k; cin >> k; pos[k].push_back(i);
}
}
for (int i = 0; i < n - 1; i++)
{
auto it = upper_bound(pos[val[i]].begin(), pos[val[i]].end(), i);
if (it != pos[val[i]].begin()) {goR[i] = *prev(it);}
else {goR[i] = -1;}
if (it != pos[val[i]].end()) {goL[i] = *it;}
else {goL[i] = n;}
if (goL[i] < n) {pq.push({goL[i], i}); ins(i);}
//cout << "Bridge " << i << " " << goL[i] << " " << goR[i] << "\n";
}
s2.insert({0, n - 1}); R[n - 1] = n - 1;
for (int i = n - 2; i >= 0; i--)
{
while (pq.size() && pq.top().fst > i)
{
del(pq.top().snd); pq.pop();
}
auto it = s1.upper_bound({goR[i] + 1, -1});
int np = goR[i] + 1;
if (it != s1.begin())
{
if (prev(it) -> fst <= goR[i] && goR[i] <= prev(it) -> snd) np = prev(it) -> snd + 2;
}
while (s2.size() && prev(s2.end()) -> fst >= np) {s2.erase(prev(s2.end()));}
if (np <= i) s2.insert({np, i});
R[i] = prev(s2.end()) -> snd;
//cout << i << " " << R[i] << "\n";
}
vector<pii> s;
for (int i = 0; i < n; i++)
{
L[i] = i;
auto it = upper_bound(s.begin(), s.end(), make_pair(R[i], n), greater<pii>());
if (it != s.end())
{
if (it == s.begin()) {L[i] = 0;}
else {L[i] = prev(it) -> snd + 1;}
}
if (i + 1 < n)
{
while (s.size() && s.back().fst <= goL[i]) {s.pop_back();}
s.push_back({goL[i], i});
}
//cout << i << " " << L[i] << " " << R[i] << "\n";
}
cin >> q;
while (q--)
{
int S, T; cin >> S >> T; S--; T--;
if (L[S] <= T && T <= R[S]) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12288 KB |
Output is correct |
| 2 |
Correct |
11 ms |
12416 KB |
Output is correct |
| 3 |
Correct |
13 ms |
12416 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
12288 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12288 KB |
Output is correct |
| 2 |
Correct |
11 ms |
12416 KB |
Output is correct |
| 3 |
Correct |
13 ms |
12416 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
12288 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
234 ms |
26352 KB |
Output is correct |
| 2 |
Correct |
278 ms |
25708 KB |
Output is correct |
| 3 |
Correct |
236 ms |
25752 KB |
Output is correct |
| 4 |
Correct |
232 ms |
25964 KB |
Output is correct |
| 5 |
Correct |
235 ms |
25964 KB |
Output is correct |
| 6 |
Correct |
202 ms |
24300 KB |
Output is correct |
| 7 |
Incorrect |
189 ms |
24364 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
12288 KB |
Output is correct |
| 2 |
Correct |
11 ms |
12416 KB |
Output is correct |
| 3 |
Correct |
13 ms |
12416 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
12288 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
