제출 #1294246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294246		flaming_top1	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	237 ms	27696 KiB

long_mansion

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;

using namespace std;

int n, a[500005], l[500005], r[500005];
vector<int> adj[500005];

bool check(int l, int r, int col)
{
    auto idx = lower_bound(adj[col].begin(), adj[col].end(), l);
    if (idx != adj[col].end())
        return l <= *idx and *idx <= r;
    return false;
}

fami lore()
{
    SPED;
    cin >> n;
    for (int i = 1; i < n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        int z;
        cin >> z;
        for (int j = 1; j <= z; j++)
        {
            int w;
            cin >> w;
            adj[w].emplace_back(i);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        l[i] = r[i] = i;
        while (true)
        {
            if (l[i] > 1 and check(l[i], r[i], a[l[i] - 1]))
            {
                r[i] = max(r[l[i] - 1], r[i]);
                l[i] = l[l[i] - 1];
            }
            else
            {
                if (check(l[i], r[i], a[r[i]]))
                    r[i]++;
                else
                    break;
            }
        }
    }

    int q;
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;

        cout << (l[u] <= v and v <= r[u] ? "YES" : "NO") << endl;
    }
}
// Let your soul wander where dreams are born.

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