# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1225766 | _rain_ | Long Mansion (JOI17_long_mansion) | C++20 | 349 ms | 88336 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=(int)5e5;
int x[N+2],y[N+2],c[N+2],b[N+2];
vector<int>arr[N+2];
int n,q;
namespace subtask3{
int lef[N+2],rig[N+2];
set<int>pos[N+2];
bool inside(int l,int r,int x){
auto it=pos[x].lower_bound(l);
if (it==pos[x].end()) return false;
return *it<=r;
}
void main_code(){
for(int i=1;i<=n;++i){
for(auto&x:arr[i]) pos[x].insert(i);
}
for(int i=1;i<=n;++i){
lef[i]=rig[i]=i;
bool nxt=true;
while (true){
if (lef[i]>1 && inside(lef[i],rig[i],c[lef[i]-1])){
rig[i]=max(rig[i],rig[lef[i]-1]);
lef[i]=lef[lef[i]-1];
}
else if (rig[i]<n && inside(lef[i],rig[i],c[rig[i]])) rig[i]++;
else break;
}
}
for(int i=1;i<=q;++i){
bool ok=(lef[x[i]] <= y[i] && y[i]<=rig[x[i]]);
cout<<(ok?"YES":"NO")<<'\n';
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
#define task "main"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin>>n;
for(int i=1;i<n;++i) cin>>c[i];
for(int i=1;i<=n;++i){
cin>>b[i];
arr[i].resize(b[i]);
for(auto&x:arr[i]) cin>>x;
}
cin>>q;
for(int i=1;i<=q;++i) cin>>x[i]>>y[i];
return subtask3::main_code(),0;
assert(false);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |