Submission #69913

#	Time	Username	Problem	Language	Result	Execution time	Memory
69913		MatheusLealV	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3061 ms	16044 KiB

long_mansion

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

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

vector<int> pos[N];

void solve(int l, int r, int i)
{
	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) solve(l, max(r + 1, R[r] + 1), 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) solve(min(l - 1, L[i]),  r, i);		
	}
}

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