제출 #1149543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149543		AHOKA	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	723 ms	57068 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define F first
#define S second
#define pii pair<int, int>
#define ppp pair<int, pii>

const int maxn = 5e5 + 10, maxm = 4e2 + 10;

int n, m, l[maxn], r[maxn], nxt[maxn], prv[maxn], last[maxn];

int c[maxn], sz[maxn];

vector<int> a[maxn];

signed main(){
    cin >> n;
    for (int i = 1; i < n;i++)
        cin >> c[i];

    for (int i = 1; i <= n;i++){
        cin >> sz[i];
        for (int j = 1; j <= sz[i]; j++){
            int x;
            cin >> x;
            a[i].push_back(x);
        }
    }

    for (int i = 1; i <= n;i++)
        last[i] = 0;

    for (int i = 1; i < n;i++){
        for(auto j : a[i])
            last[j] = i;

        prv[i] = last[c[i]];
    }

    for (int i = 1; i <= n;i++)
        last[i] = n + 1;

    for (int i = n; i > 1; i--)
    {
        for(auto j : a[i])
            last[j] = i;

        nxt[i - 1] = last[c[i - 1]];
    }

    for (int i = 1; i <= n;i++){
        l[i] = r[i] = i;
        while(1){
            if(1 < l[i] && nxt[l[i] - 1] <= r[i]){
                r[i] = max(r[i], r[l[i] - 1]);
                l[i] = min(l[i], l[l[i] - 1]);
            }

            if(r[i] < n && l[i] <= prv[r[i]]){
                r[i]++;
            }

            if(!(r[i] < n && l[i] <= prv[r[i]]) && !(1 < l[i] && nxt[l[i] - 1] <= r[i]))
                break;
        }
    }

    cin >> m;

    while(m--){
        int s, f;
        cin >> s >> f;
        if(l[s] <= f && f <= r[s])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

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