Submission #1092770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092770		12345678	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	201 ms	52476 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, lstl[nx], lstr[nx], l[nx], r[nx], x, y, qrs, lst[nx], c[nx];
vector<int> d[nx];

void solve(int vl, int vr)
{
    if (vl==vr) return l[vl]=r[vl]=vl, void();
    int md=(vl+vr)/2, cl=md, cr=md;
    solve(vl, md);
    solve(md+1, vr);
    for (int i=md; i>=vl; i--)
    {
        if (r[i]==md)
        {
            cl=min(cl, l[i]);
            while (1)
            {
                if (vl<cl&&lstr[cl]<=cr) cl--;
                else if (cr<vr&&lstl[cr]>=cl) cr++;
                else break;
            }
            l[i]=cl;
            r[i]=cr;
        }
    }
    cl=cr=md+1;
    for (int i=md+1; i<=vr; i++)
    {
        if (l[i]==md+1)
        {
            cr=max(cr, r[i]);
            while (1)
            {
                if (vl<cl&&lstr[cl]<=cr) cl--;
                else if (cr<vr&&lstl[cr]>=cl) cr++;
                else break;
            }
            l[i]=cl;
            r[i]=cr;
        }
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<n; i++) cin>>c[i];
    for (int i=1; i<=n; i++)
    {
        cin>>x;
        for (int j=1; j<=x; j++) cin>>y, d[i].push_back(y);
    }
    for (int i=1; i<n; i++)
    {
        for (auto x:d[i]) lst[x]=i;
        lstl[i]=lst[c[i]];
    }
    for (int i=1; i<=n; i++) lst[i]=n+1;
    for (int i=n; i>1; i--)
    {
        for (auto x:d[i]) lst[x]=i;
        lstr[i]=lst[c[i-1]];
    }
    solve(1, n);
    cin>>qrs;
    while (qrs--)
    {
        cin>>x>>y;
        if (l[x]<=y&&y<=r[x]) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

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