#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 5e5+20,mod = 998244353;
constexpr ll inf = 1e18+10;
inline int mkay(int a,int b){
if (a+b >= mod) return a+b-mod;
if (a+b < 0) return a+b+mod;
return a+b;
}
inline int poww(int a,int k){
if (k < 0) return 0;
int z = 1;
while (k){
if (k&1) z = 1ll*z*a%mod;
a = 1ll*a*a%mod;
k >>= 1;
}
return z;
}
int c[N],n;
vector<int> key[N];
bool st[N],en[N];
pll baz[N];
int par[N];
int getpar(int v){
if (par[v] == v) return v;
return par[v] = getpar(par[v]);
}
void mg(int u,int v){
u = getpar(u);
v = getpar(v);
if (u == v) return;
par[u] = v;
baz[v].X = min(baz[u].X,baz[v].X);
baz[v].Y = min(baz[u].Y,baz[v].Y);
}
void rlx(int v){
st[v] = 1;
baz[v] = {v,v};
int l = v,r = v;
while (1){
bool fl = 0;
while (r < n){
int k = c[r];
if (key[k].empty() || key[k].back() < l) break;
int j = lower_bound(all(key[k]),l) - key[k].begin();
if (key[k][j] > r) break;
fl = 1;
if (!st[r+1]){
rlx(r+1);
int p = getpar(r+1);
r = max(r,baz[p].Y);
l = min(l,baz[p].X);
int p2 = getpar(v);
baz[p2].X = min(l,baz[p2].X);
baz[p2].Y = max(r,baz[p2].Y);
baz[v] = baz[p2];
l = baz[v].X;
r = baz[v].Y;
continue;
}
if (en[r+1]){
int p = getpar(r+1);
r = max(r,baz[p].Y);
l = min(l,baz[p].X);
int p2 = getpar(v);
baz[p2].X = min(l,baz[p2].X);
baz[p2].Y = max(r,baz[p2].Y);
baz[v] = baz[p2];
l = baz[v].X;
r = baz[v].Y;
continue;
}
mg(v,r+1);
int p = getpar(v);
baz[v] = baz[p];
l = baz[v].X;
r = baz[v].Y;
}
while (l > 1){
int k = c[l-1];
if (key[k].empty() || key[k].back() < l) break;
int j = lower_bound(all(key[k]),l) - key[k].begin();
if (key[k][j] > r) break;
fl = 1;
if (!st[l-1]){
rlx(l-1);
int p = getpar(l-1);
r = max(r,baz[p].Y);
l = min(l,baz[p].X);
int p2 = getpar(v);
baz[p2].X = min(l,baz[p2].X);
baz[p2].Y = max(r,baz[p2].Y);
baz[v] = baz[p2];
l = baz[v].X;
r = baz[v].Y;
continue;
}
if (en[l-1]){
int p = getpar(l-1);
int p2 = getpar(v);
baz[p2].X = min(baz[p].X,baz[p2].X);
baz[p2].Y = max(baz[p].Y,baz[p2].Y);
baz[v] = baz[p2];
l = baz[v].X;
r = baz[v].Y;
continue;
}
mg(v,l-1);
int p = getpar(v);
baz[v] = baz[p];
l = baz[v].X;
r = baz[v].Y;
}
if (!fl) break;
}
en[v] = 1;
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
rep(i,1,n) cin >> c[i];
rep(i,1,n+1){
par[i] = i;
int sz;
cin >> sz;
rep(j,0,sz){
int t;
cin >> t;
key[t].pb(i);
}
}
rep(i,1,n+1) if (!st[i]){
rlx(i);
}
rep(i,1,n+1){
int j = getpar(i);
baz[i] = baz[j];
}
int q;
cin >> q;
while (q--){
int x,y;
cin >> x >> y;
if (y >= baz[x].X && y <= baz[x].Y)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3076 ms |
12156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3076 ms |
12156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3059 ms |
17068 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3076 ms |
12156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
