Submission #1081932

#TimeUsernameProblemLanguageResultExecution timeMemory
1081932daoquanglinh2007Long Mansion (JOI17_long_mansion)C++98
100 / 100
179 ms43088 KiB
#include <bits/stdc++.h>
using namespace std;
 
const int NM = 5e5;
 
int N, Q, C[NM+5], B[NM+5], pre[NM+5], nxt[NM+5], lst[NM+5];
vector <int> arr[NM+5];
int l[NM+5], r[NM+5];
 
void solve(int u){
    int curl = u, curr = u;
    while (true){
        if (curl > 1 && nxt[curl] <= curr){
            curl--;
            if (r[curl] >= u){
                l[u] = l[curl];
                r[u] = r[curl];
                return;
            }
        }
        else if (curr < N && pre[curr] >= curl){
            curr++;
        }
        else break;
    }
    l[u] = curl, r[u] = curr;
}
 
int 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++){
        cin >> B[i];
        arr[i].resize(B[i]);
        for (int j = 0; j < B[i]; j++) cin >> arr[i][j];
    }
    for (int i = 1; i < N; i++){
        for (int x : arr[i]) lst[x] = i;
        pre[i] = lst[C[i]];
    }
    for (int i = 1; i <= N; i++) lst[i] = N+1;
    for (int i = N; i > 1; i--){
        for (int x : arr[i]) lst[x] = i;
        nxt[i] = lst[C[i-1]];
    }
    for (int i = 1; i <= N; i++) solve(i);
 
    cin >> Q;
    while (Q--){
        int x, y; cin >> x >> y;
        if (l[x] <= y && r[x] >= y){
            cout << "YES\n";
            continue;
        }
        cout << "NO\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...