제출 #128369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128369		doowey	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	386 ms	52344 KiB

long_mansion

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)5e5 + 9;
int L[N];
int R[N];
int C[N];
vector<int> ls[N];

int las[N];
int lf[N];
int rf[N];


int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i < n; i ++ ){
        cin >> C[i];
    }
    int x, k;
    for(int i = 1; i <= n ; i ++ ){
        cin >> k;
        for(int j = 0 ; j < k ; j ++ ){
            cin >> x;
            ls[i].push_back(x);
        }
    }
    for(int j = 1; j <= n; j ++ )
        las[j] = -1;
    for(int i = 1; i < n; i ++ ){
        for(auto p : ls[i])
            las[p] = i;
        lf[i + 1] = las[C[i]];
    }
    for(int j = 1; j <= n; j ++ )
        las[j] = -1;
    for(int i = n; i > 1; i -- ){
        for(auto p : ls[i])
            las[p] = i;
        rf[i - 1] = las[C[i - 1]];
    }
    for(int i = 1; i <= n; i ++ ){
        L[i] = i;
        R[i] = i;
        while(1){
            if(L[i] != 1 && rf[L[i] - 1] <= R[i] && rf[L[i] - 1] != -1){
                R[i] = max(R[i], R[L[i]-1]);
                L[i] = min(L[i], L[L[i]-1]);
            }
            else if(R[i] != n && lf[R[i] + 1] >= L[i] && lf[R[i] + 1] != -1){
                R[i] ++ ;
            }
            else{
                break;
            }
        }
    }
    int Q;
    cin >> Q;
    int p, q;
    for(int i = 0 ; i < Q; i ++ ){
        cin >> p >> q;
        if(q >= L[p] && q <= R[p])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

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