Submission #69919

#	Time	Username	Problem	Language	Result	Execution time	Memory
69919		MatheusLealV	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3047 ms	18804 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];

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, R[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);
        }
    }

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

            if(q)  e[i] = j;

            else 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: 0 / 15
• Subtask 4: 0 / 75