Submission #69917

#	Time	Username	Problem	Language	Result	Execution time	Memory
69917		MatheusLealV	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	3056 ms	6696 KiB

long_mansion

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

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

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++)
    {

        d[i] = i;

        e[i] = i;

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

            if(q) d[i] = j;

            else break;
        }

        for(int j = i + 1; j <= n; j++)
        {
            int q = upper_bound(pos[c[j - 1]].begin(), pos[c[j - 1]].end(), j) - 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++)
    {
       // cout<<"SOLVE "<<i<<"\n";
        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] = R[i - 1];

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