Submission #69926

#	Time	Username	Problem	Language	Result	Execution time	Memory
69926		MatheusLealV	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	608 ms	68888 KiB

long_mansion

#include <bits/stdc++.h>
#define N 500050
using namespace std;

int n, q, c[N], L[N], R[N];

int e[N];

vector<int> pos[N], T[N];

void solve(int l, int r, int i)
{
    while(true)
    {
        L[i] = l;

        R[i] = r;

        bool ok = false;

        if(r < n)
        {
            int q = upper_bound(pos[c[r]].begin(), pos[c[r]].end(), r) - lower_bound(pos[c[r]].begin(), pos[c[r]].end(), l);
            
            if(q) r = max(r + 1, e[r]), ok = 1;//solve(l, max(r + 1, R[r]), i), ok = 1;
        }

        if(l > 1 and !ok)
        {
            int q = upper_bound(pos[c[l - 1]].begin(), pos[c[l - 1]].end(), r) - lower_bound(pos[c[l - 1]].begin(), pos[c[l - 1]].end(), l);

            if(q) l = min(l - 1, L[l]), ok = 1;;//solve(min(l - 1, L[l]), r, i);        
        }

        if(!ok) break;
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n;

    for(int i = 1; i < n; i++) cin>>c[i];

    for(int i = 1; i <= n; i++)
    {
        L[i] = R[i] = i;

        int a, b;

        cin>>a;

        for(int x = 1; x <= a; x++)
        {
            cin>>b;

            pos[b].push_back(i);

            T[i].push_back(b);
        }
    }

    for(int i = n; i >= 1; i--)
    {
    	e[i] = i;

    	for(auto x: T[i])
    	{
    		if(x == c[i])
    		{
    			e[i] = e[i + 1];

    			while(e[i] <= n)
    			{
           			 int q = upper_bound(pos[c[e[i]]].begin(), pos[c[e[i]]].end(), e[i]) - lower_bound(pos[c[e[i]]].begin(), pos[c[e[i]]].end(), i);

           			 if(q) e[i] = e[e[i] + 1];

           			 else break;
    			}

    			break;
    		}
    	}
 
    }

    for(int i = 1; i <= n; i++)
    {
        if(L[i - 1] <= i and i <= R[i - 1])
        {
            int q = upper_bound(pos[c[i - 1]].begin(), pos[c[i - 1]].end(), e[i]) - lower_bound(pos[c[i - 1]].begin(), pos[c[i - 1]].end(), i);

            if(q) L[i] = L[i - 1], R[i] = max(R[i - 1], e[i]);

            else L[i] = i, R[i] = e[i];
        }

       else solve(i, i, i);
    }

    cin>>q;

    for(int i = 1; i <= q; i++)
    {
        int x, y;

        cin>>x>>y;

        if(L[x] <= y and 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