Submission #1234477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234477		ElyesChaabouni	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	256 ms	63512 KiB

long_mansion

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define INV_2 499122177
#define INV_2_MOD2 500000004
#define INV_6_MOD2 1666666612
#define INF 1000000001
#define PI 3.1415926535129793231246
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007

using namespace std;

int tree[(1<<20)+1], p = (1<<19);

int n, c[500005], prvL[500005], prvR[500005], l[500005], r[500005], b[500005];
vector<int>v[500005], keys[500005];

void init()
{
	for(int i = 0; i < n-1; i++)
	{
		for(int j = 0; j < b[i]; j++)
			v[keys[i][j]].push_back(i);
		if(v[c[i]].empty())
			prvL[i+1]=-1;
		else
			prvL[i+1]=v[c[i]].back();
	}
	for(int i = 0; i <= 500000; i++)
		v[i].clear();
	for(int i = n-1; i >= 1; i--)
	{
		for(int j = 0; j < b[i]; j++)
			v[keys[i][j]].push_back(i);
		if(v[c[i-1]].empty())
			prvR[i-1]=n+1;
		else
			prvR[i-1]=v[c[i-1]].back();
	}
	for(int i = 0; i < 2*p+1; i++)
		tree[i]=-1;
	for(int i = 1; i < n; i++)
		tree[i+p]=prvL[i];
	for(int i = p-1; i >= 1; i--)
		tree[i]=min(tree[2*i], tree[2*i+1]); 
}

int query(int x, int y)
{
	x+=p;
	y+=p;
	int res=INF;
	while(x <= y)
	{
		if(x%2)
		{
			res=min(res, tree[x]);
			x++;
		}
		if(y%2==0)
		{
			res = min(res, tree[y]);
			y--;
		}
		x/=2;
		y/=2;
	}
	return res;
}

int first_idx_less_than(int x, int y, int val)
{
	x+=p;
	y+=p;
	int res=n, idx;
	while(x <= y)
	{
		if(x%2)
		{
			if(tree[x] < val)
			{
				idx=x;
				while(idx < p)
				{
					if(tree[2*idx] < val)
						idx*=2;
					else
						idx=idx*2+1;
				}
				res=min(res, idx-p);
			}
			x++;
		}
		if(y%2==0)
		{
			if(tree[y] < val)
			{
				idx=y;
				while(idx < p)
				{
					if(tree[2*idx] < val)
						idx*=2;
					else
						idx=idx*2+1;
				}
				res=min(res, idx-p);
			}
			y--;
		}
		x/=2;
		y/=2;
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> n;
	for(int i = 0; i < n-1; i++)
		cin >> c[i];
	for(int i = 0; i < n; i++)
	{
		cin >> b[i];
		keys[i].resize(b[i]);
		for(int j = 0; j < b[i]; j++)
		{
			cin >> keys[i][j];
		}
	}
	init();
	/*for(int i = 0; i < n; i++)
		cout << prvL[i] << ' ';
	cout << '\n';

	for(int i = 0; i < n; i++)
		cout << prvR[i] << ' ';
	cout << '\n';*/
	for(int i = 0; i < n; i++)
	{
		l[i]=i;
		while(l[i] && query(i+1, prvR[l[i]-1]) >= l[i])
			l[i]=l[l[i]-1];
		r[i]=first_idx_less_than(i+1, n-1, l[i])-1;
		//cout << l[i] << ' ' << r[i] << '\n';
	}
	int q;
	cin >> q;
	while(q--)
	{
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		if(y >= l[x] && y <= r[x])
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}
//07-02-46

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