Submission #1262711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262711		erering	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	170 ms	66444 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
const int N=5e5+5,inf=1e18;
int c[N],l[N],r[N],last[N],n;
pair<int,int> ans[N];
bool vis[N];
void solve(int i){
    if(vis[i])return;
    ans[i]={i,i};
    vis[i]=1;
    while(1){
        //if(i==3)cout<<ans[i].first<<' '<<ans[i].second<<' '<<l[ans[i].second+1]<<endl;
        if(ans[i].first>1 && r[ans[i].first-1]>=ans[i].first && r[ans[i].first-1]<=ans[i].second){
            solve(ans[i].first-1);
            ans[i].second=max(ans[i].second,ans[ans[i].first-1].second);
            ans[i].first=min(ans[i].first,ans[ans[i].first-1].first);
        }
        else if(ans[i].second<n && l[ans[i].second+1]>=ans[i].first && l[ans[i].second+1]<=ans[i].second){
            solve(ans[i].second+1);
            ans[i].first=min(ans[i].first,ans[ans[i].second+1].first);
            ans[i].second=max(ans[i].second,ans[ans[i].second+1].second);
        }
        else break;
    }
}
vector<int> keys[N];
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)cin>>c[i];
    for(int i=1;i<=n;i++){
        if(i>1)l[i]=last[c[i-1]];
        int k; cin>>k;
        for(int j=0;j<k;j++){
            int x; cin>>x; keys[i].pb(x);
            last[x]=i;
        }
    }
    for(int i=0;i<N;i++)last[i]=inf;
    for(int i=n;i>=1;i--){
        if(i<n)r[i]=last[c[i]];
        for(int j=0;j<keys[i].size();j++){
            last[keys[i][j]]=i;
        }
    }
    for(int i=1;i<=n;i++)solve(i);
    int q; cin>>q;
    while(q--){
        int x,y; cin>>x>>y;
        if(ans[x].first<=y && ans[x].second>=y)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75