Submission #1110009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110009		Warinchai	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	275 ms	37192 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
int c[500005];
vector<int>key[500005];
int l[500005];
int r[500005];
int have[500005];
vector<int>del;
void upd(int i,int &curl,int &curr,int st,int en){
    while(1){
        int check=0;
        while(curr<en&&have[c[curr]]){
            curr++;
            for(auto a:key[curr])if(!(have[a]++))del.push_back(a);
            check=1;
        }
        while(curl>st&&have[c[curl-1]]){
            curl--;
            for(auto a:key[curl])if(!(have[a]++))del.push_back(a);
            check=1;
        }
        if(!check)break;
    }
    r[i]=curr;
    l[i]=curl;
}
void solve(int st,int en){
    int m=(st+en)/2;
    if(st==en)return l[m]=m,r[m]=m,void();
    vector<pair<int,int>>ll,lr,rl,rr;
    solve(st,m);
    solve(m+1,en);
    int curr=m,curl=m+1;
    for(int i=m;i>=st;i--){
        if(r[i]<m)continue;
        while(curl>st&&curl>l[i]){
            curl--;
            for(auto a:key[curl])if(!(have[a]++))del.push_back(a);
        }
        upd(i,curl,curr,st,en);
    }
    for(auto x:del)have[x]=0;
    del.clear();
    curr=m,curl=m+1;
    for(int i=m+1;i<=en;i++){
        if(l[i]>m+1)continue;
        while(curr<en&&curr<r[i]){
            curr++;
            for(auto a:key[curr])if(!(have[a]++))del.push_back(a);
        }
        upd(i,curl,curr,st,en);
    }
    for(auto x:del)have[x]=0;
    del.clear();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<n;i++)cin>>c[i];
    for(int i=1;i<=n;i++){
        int b;cin>>b;
        for(int j=0;j<b;j++){
            int x;cin>>x;
            key[i].push_back(x);
        }
    }
    solve(1,n);
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int x,y;cin>>x>>y;
        if(y>=l[x]&&y<=r[x])cout<<"YES\n";
        else cout<<"NO\n";
    }
}

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