제출 #1065793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065793		Unforgettablepl	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3038 ms	11600 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> C(N+1);
    for(int i=1;i<N;i++)cin>>C[i];
    vector<vector<int>> keys(N+1);
    for(int i=1;i<=N;i++) {
        int b;cin>>b;
        keys[i].resize(b);
        for(int&j:keys[i])cin>>j;
    }
    vector<int> Lbound(N+1);
    vector<int> Rbound(N+1);
    for(int i=1;i<=N;i++) {
        int L = i;
        int R = i;
        vector<bool> have_key(N+1);
        for(int&x:keys[R])have_key[x]=true;
        while(true) {
            if(R!=N and have_key[C[R]]) {
                R++;
                for(int&x:keys[R])have_key[x]=true;
            } else if(L!=1 and have_key[C[L-1]]) {
                L--;
                for(int&x:keys[L])have_key[x]=true;
            } else break;
        }
        Lbound[i]=L;
        Rbound[i]=R;
    }
    int Q;
    cin >> Q;
    for(int i=1;i<=Q;i++) {
        int X,Y;cin>>X>>Y;
        if(Lbound[X]<=Y and Y<=Rbound[X])cout<<"YES\n";
        else cout << "NO\n";
    }
}

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