#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<int, int>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
const ll N = 5e5 + 100;
const ll inf = 1e8;
const ll mod = 1e9 + 7;
const ll block = 230;
ll n, q;
ll c[N];
map<ll,ll>pos;
ll L[N][20], R[N][20], l[N], r[N], lg[N];
struct segment_tree_max{
ll n;
vector<ll>st;
void init(ll _n){
n = _n;
st.clear(); st.resize(4 * n + 10, -inf);
}
void update(ll id, ll l, ll r, ll left, ll right, ll val){
if(l > right || r < left) return;
if(left <= l && r <= right){
st[id] = max(st[id], val);
return;
}
ll mid = (l + r) / 2;
update(2 * id, l, mid, left, right, val);
update(2 * id + 1, mid + 1, r, left, right, val);
st[id] = max(st[2 * id], st[2 * id + 1]);
}
ll get(ll id, ll l, ll r, ll left, ll right){
if(l > right || r < left) return -inf;
if(left <= l && r <= right) return st[id];
ll mid = (l + r) / 2;
return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
}
void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
ll get(ll l, ll r){return get(1,1,n,l,r);}
} stmax;
struct segment_tree_min{
ll n;
vector<ll>st;
void init(ll _n){
n = _n;
st.clear(); st.resize(4 * n + 10, inf);
}
void update(ll id, ll l, ll r, ll left, ll right, ll val){
if(l > right || r < left) return;
if(left <= l && r <= right){
st[id] = min(st[id], val);
return;
}
ll mid = (l + r) / 2;
update(2 * id, l, mid, left, right, val);
update(2 * id + 1, mid + 1, r, left, right, val);
st[id] = min(st[2 * id], st[2 * id + 1]);
}
ll get(ll id, ll l, ll r, ll left, ll right){
if(l > right || r < left) return inf;
if(left <= l && r <= right) return st[id];
ll mid = (l + r) / 2;
return min(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
}
void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
ll get(ll l, ll r){return get(1,1,n,l,r);}
} stmin;
vector<ll>g[N];
ll get_L(ll l, ll r){
ll p = lg[r - l + 1];
return min(L[l][p], L[r - (1 << p) + 1][p]);
}
ll get_R(ll l, ll r){
ll p = lg[r - l + 1];
return max(R[l][p], R[r - (1 << p) + 1][p]);
}
void build(){
for(int i = 1; i <= n;i++){
if(i >= 2) L[i][0] = (pos[c[i - 1]] == 0 ? -inf : pos[c[i-1]]);
else L[i][0] = -inf;
for(auto x : g[i]) pos[x] = i;
}
pos.clear();
for(int i = n; i >= 1;i--){
if(i <= n - 1) R[i][0] = (pos[c[i]] == 0 ? inf : pos[c[i]]);
else R[i][0] = inf;
for(auto x : g[i]) pos[x] = i;
}
for(int j = 1; j <= 19;j++){
for(int i = 1; i + (1 << j) <= n + 1;i++){
L[i][j] = min(L[i][j-1], L[i + (1 << (j - 1))][j-1]);
R[i][j] = max(R[i][j-1], R[i + (1 << (j - 1))][j-1]);
}
}
for(int i = 1; i <= n;i++){
ll x = i, y = i;
while(1){
pll lst = {x, y};
if(x > 1){
ll l = 1, r = x - 1, pos = -1;
while(l <= r){
ll mid = (l + r) / 2;
if(get_R(mid, x) <= y) pos = mid, r = mid - 1;
else l = mid + 1;
}
if(pos != -1){
ll mn = stmin.get(pos, y), mx = stmax.get(pos, y);
x = min({x, mn, pos}); y = max(y, mx);
}
}
if(y < n){
ll l = y + 1, r = n, pos = -1;
while(l <= r){
ll mid = (l + r) / 2;
if(get_L(y, mid) >= x) pos = mid, l = mid + 1;
else r = mid - 1;
}
if(pos != -1){
ll mn = stmin.get(x, pos), mx = stmax.get(x, pos);
x = min(x, mn); y = max({y, mx, pos});
}
}
if(lst.F == x && lst.S == y) break;
}
l[i] = x, r[i] = y;
stmin.update(i, i, l[i]); stmax.update(i, i, r[i]);
}
}
void to_thic_cau(){
cin >> n;
for(int i = 1; i <= n;i++) lg[i] = __lg(i);
for(int i = 1; i <= n - 1;i++) cin >> c[i];
for(int i = 1; i <= n;i++){
ll sz; cin >> sz;
for(int j = 1; j <= sz;j++){
ll x; cin >> x;
g[i].pb(x);
}
}
build();
cin >> q;
while(q--){
ll x,y; cin >> x >> y;
if(l[x] <= y && y <= r[x]) cout << "YES" << '\n';
else cout << "NO" << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
34640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
