Submission #1266265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266265		tvgk	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	251 ms	35480 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 5e5 + 7;

int n, a[mxN], tree[mxN * 4], l[mxN], r[mxN], lck[mxN];
vector<int> key[mxN];

void Build(int j = 1, int l = 1, int r = n + 1)
{
    if (l == r)
    {
        tree[j] = a[l];
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    tree[j] = min(tree[j * 2], tree[j * 2 + 1]);
}

int Walk(int vt, int ed, int j = 1, int l = 1, int r = n + 1)
{
    if (r <= vt || ed <= tree[j])
        return 0;

    if (l == r)
        return l - 1;

    int mid = (l + r) / 2;
    int res = Walk(vt, ed, j * 2, l, mid);
    if (res)
        return res;
    return Walk(vt, ed, j * 2 + 1, mid + 1, r);
}

bool Got(int l, int r, int id)
{
    auto tmp = lower_bound(key[id].begin(), key[id].end(), l);
    return (tmp != key[id].end() && *tmp <= r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 2; i <= n; i++)
        cin >> lck[i];

    for (int i = 1; i <= n; i++)
    {
        int num;
        cin >> num;

        if (key[lck[i]].size())
            a[i] = key[lck[i]].back();

        for (int j = 1; j <= num; j++)
        {
            int tmp;
            cin >> tmp;
            key[tmp].push_back(i);
        }
    }
    Build();

    for (int i = 1; i <= n; i++)
    {
        l[i] = r[i] = i;

        while (1)
        {
            r[i] = max(r[i], Walk(r[i], l[i]));

            if (Got(l[i], r[i], lck[l[i]]))
            {
                r[i] = max(r[i], r[l[i] - 1]);
                l[i] = l[l[i] - 1];
            }
            else
                break;
        }
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;

        if (l[u] <= v && v <= r[u])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

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