#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,q;
int arr[500005];
vector<int> keys[500005];
ii queries[500005];
bool ans[500005];
int lpos[500005];
int rpos[500005];
int has[500005];
int bad[500005];
int main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n;
rep(x,1,n) cin>>arr[x];
int a,b;
rep(x,1,n+1){
cin>>a;
rep(y,0,a){
cin>>b;
keys[x].pub(b);
}
}
cin>>q;
rep(x,0,q) cin>>queries[x].fi>>queries[x].se;
rep(zzz,0,2){ //change to 2 later
rep(x,0,500005) has[x]=1e9;
rep(x,n,1){
for (auto &it:keys[x+1]) has[it]=x;
lpos[x]=has[arr[x]];
}
rep(x,0,500005) has[x]=-1e9;
rep(x,1,n){
for (auto &it:keys[x]) has[it]=x;
rpos[x+1]=has[arr[x]];
}
//rep(x,1,n+1) cout<<lpos[x]<<" "; cout<<endl;
//rep(x,1,n+1) cout<<rpos[x]<<" "; cout<<endl;
memset(bad,-1,sizeof(bad));
rep(x,1,n){
rep(y,x+2,n+1){
if (lpos[x]>=y && x>=rpos[y]) bad[x]=y;
}
if (lpos[x]==1e9) bad[x]=1e9;
}
//rep(x,1,n+1) cout<<bad[x]<<" "; cout<<endl<<endl;
rep(x,0,q) if (queries[x].se<queries[x].fi){
//cout<<"query: "<<x<<endl;
bool can=true;
rep(y,queries[x].se,queries[x].fi){
//cout<<y<<" "<<bad[y]<<endl;
if (queries[x].fi<bad[y]) can=false;
}
ans[x]=can;
}
//flip shit now
reverse(arr+1,arr+n);
reverse(keys+1,keys+n+1);
rep(x,0,q) tie(queries[x].fi,queries[x].se)=ii(n-queries[x].fi+1,n-queries[x].se+1);
}
rep(x,0,q){
if (ans[x]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
16204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
16204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3083 ms |
28756 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
16204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
