Submission #1291477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291477		kkkk	Long Mansion (JOI17_long_mansion)	C++20	0 / 100	2065 ms	5596 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n,a[N],c[N],L[N],R[N];
vector<int> d[N];
bool check(int l,int r,int v)
{
    if(d[v].empty())
        return 0;
   auto it = lower_bound(d[v].begin(),d[v].end(),l);
   if(it == d[v].end())
    return 0;
   return *it <= r;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1;i < n;i++)
        cin>>c[i];
    for(int i = 1;i <= n;i++)
    {
        int x;
        cin>>x;
        for(int j = 1;j <= x;j++)
        {
            int r;
            cin>>r;
            d[r].push_back(i);
        }
    }
    for(int i = 1;i <= n;i++)
    {
        bool cc = 1;
        int x = i,y = i;
        while(cc and x >= 1 and y <= n)
        {
            cc = 0;
            if(check(x,y,c[x-1]))
            {
                x = min(x,L[x-1]);
                y = max(y,R[x-1]);
                cc = 1;
            }
         if(check(x,y,c[y]))
           {
            y++;
            cc = 1;
           }
        }
        L[i] = x;
        R[i] = y;
    }
    int q;
    cin>>q;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        if(L[l] <= r and r <= R[l])
            cout<<"YES"<<'\n';
        else
            cout<<"NO"<<'\n';
    }
}

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