제출 #1081648

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

long_mansion

#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--;
            curl = min(curl, l[curl]);
            curr = max(curr, r[curr]);
        }
        else if (curr < N && pre[curr] >= curl){
            if (l[pre[curr]] <= u && r[pre[curr]] >= u){
                l[u] = l[pre[curr]];
                r[u] = r[pre[curr]];
                return;
            }
            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;
}

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