Submission #1261783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261783		chikien2009	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	144 ms	46332 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, q, a, x;
int c[500000], ln[500000], rn[500000], last[500000], l[500000], r[500000];
bool check[500000];
vector<int> b[500000];

inline void Form(int inp)
{
    if (!check[inp])
    {
        check[inp] = true;
        while (true)
        {
            if (l[inp] > 0 && l[inp] && rn[l[inp] - 1] <= r[inp])
            {
                Form(l[inp] - 1);
                r[inp] = max(r[inp], r[l[inp] - 1]);
                l[inp] = min(l[inp], l[l[inp] - 1]);
            }
            else if (r[inp] + 1 < n && l[inp] <= ln[r[inp] + 1])
            {
                Form(r[inp] + 1);
                l[inp] = min(l[inp], l[r[inp] + 1]);
                r[inp] = max(r[inp], r[r[inp] + 1]);
            }
            else
            {
                break;
            }
        }
    }
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> c[i];
        c[i]--;
    }
    fill_n(last, 500000, -1);
    for (int i = 0; i < n; ++i)
    {
        cin >> a;
        l[i] = r[i] = i;
        b[i].resize(a);
        ln[i] = (i == 0 || last[c[i - 1]] == -1 ? -1 : last[c[i - 1]]);
        for (int j = 0; j < a; ++j)
        {
            cin >> b[i][j];
            b[i][j]--;
            last[b[i][j]] = i;
        }
    }
    fill_n(last, 500000, -1);
    for (int i = n - 1; i >= 0; --i)
    {
        rn[i] = (i == n - 1 || last[c[i]] == -1 ? 1e9 : last[c[i]]);
        for (auto &j : b[i])
        {
            last[j] = i;
        }
    }
    for (int i = 0; i < n; ++i)
    {
        Form(i);
    }
    cin >> q;
    while (q--)
    {
        cin >> a >> x;
        a--;
        x--;
        cout << (l[a] <= x && x <= r[a] ? "YES" : "NO") << "\n";
    }
    return 0;
}

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