Submission #120369

#	Time	Username	Problem	Language	Result	Execution time	Memory
120369		aminra	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	2758 ms	68220 KiB

long_mansion

//Soon, you will understand ... ;)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)998244353;
const int MAXN = (int)5e5 + 3;
const int infint = (int)1e9 + 3;
const ll inf = (ll)1e12;
int n, c[MAXN], canr[MAXN], canl[MAXN], last[MAXN], minl[MAXN], maxr[MAXN], q;
vector<int> B[MAXN];
bool extendable(int l, int r)
{
	return (canl[r] < l && r < canr[l]) ? 0 : 1;
}
int seg[4 * MAXN], seg2[4 * MAXN];
void build(int node, int st, int en)
{
	if(en - st < 2)
	{
		seg[node] = canr[st];
		return;
	}
	int mid = (st + en) >> 1;
	build(node << 1, st, mid);
	build(node << 1 | 1, mid, en);
	seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
	return;
}
int get(int node, int st, int en, int l, int r)
{
	if(l >= en || st >= r)
		return 0;
	if(l <= st && en <= r)
		return seg[node];
	int mid = (st + en) >> 1;
	return max(get(node << 1, st, mid, l, r), get(node << 1 | 1, mid, en, l, r));
}
void build3(int node, int st, int en)
{
	if(en - st < 2)
	{
		seg2[node] = canl[st];
		return;
	}
	int mid = (st + en) >> 1;
	build3(node << 1, st, mid);
	build3(node << 1 | 1, mid, en);
	seg2[node] = min(seg2[node << 1], seg2[node << 1 | 1]);
	return;
}
int get3(int node, int st, int en, int l, int r)
{
	if(l >= en || st >= r)
		return infint;
	if(l <= st && en <= r)
		return seg2[node];
	int mid = (st + en) >> 1;
	return min(get3(node << 1, st, mid, l, r), get3(node << 1 | 1, mid, en, l, r));
}
void build2(int node, int st, int en)
{
	if(en - st < 2)
	{
		seg[node] = minl[st];
		return;
	}
	int mid = (st + en) >> 1;
	build2(node << 1, st, mid);
	build2(node << 1 | 1, mid, en);
	seg[node] = min(seg[node << 1], seg[node << 1 | 1]);
	return;
}
int get2(int node, int st, int en, int l, int r)
{
	if(l >= en || st >= r || l >= r)
		return infint;
	if(l <= st && en <= r)
		return seg[node];
	int mid = (st + en) >> 1;
	return min(get2(node << 1, st, mid, l, r), get2(node << 1 | 1, mid, en, l, r));
}
void build4(int node, int st, int en)
{
	if(en - st < 2)
	{
		seg2[node] = maxr[st];
		return;
	}
	int mid = (st + en) >> 1;
	build4(node << 1, st, mid);
	build4(node << 1 | 1, mid, en);
	seg2[node] = max(seg2[node << 1], seg2[node << 1 | 1]);
	return;
}
int get4(int node, int st, int en, int l, int r)
{
	if(l >= en || st >= r || l >= r)
		return 0;
	if(l <= st && en <= r)
		return seg2[node];
	int mid = (st + en) >> 1;
	return max(get4(node << 1, st, mid, l, r), get4(node << 1 | 1, mid, en, l, r));
}
int ask(int l, int r)
{
	int L = l - 1, R = r + 1;
	while(R - L > 1)
	{
		int mid = (R + L) >> 1;
		if(get(1, 1, n + 1, l, mid + 1) > r)
			R = mid;
		else
			L = mid;	
	}
	return R;
}
int ask2(int l, int r)
{
	int L = l - 1, R = r + 1;
	while(R - L > 1)
	{
		int mid = (R + L) >> 1;
		if(get3(1, 1, n + 1, mid, r + 1) < l)
			L = mid;
		else
			R = mid;
	}
	return L;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n - 1; i++)
		cin >> c[i];
	for (int i = 1; i <= n; i++)
	{
		int sz;
		cin >> sz;
		while(sz--)
		{
			int x;
			cin >> x;
			B[i].push_back(x);
		}
	}
	//canr update!
	for (int i = 1; i <= n; i++)
		last[i] = n + 1;
	for (int i = n - 1; i >= 1; i--)
	{
		for (auto u : B[i + 1])
			last[u] = i + 1;
		canr[i] = last[c[i]];
	}
	for (int i = n; i >= 1; i--)
		canr[i] = canr[i - 1];
	canr[1] = n + 1;
	
	//canl update!
	for (int i = 1; i <= n; i++)
		last[i] = 0;
	for (int i = 1; i <= n - 1; i++)	
	{
		for (auto u : B[i])
			last[u] = i;
		canl[i] = last[c[i]];
	}
	canl[n] = 0;
	
	//[l, r] is not extendable iff canl[r] < l <= r < canr[l]
	//minl is min l such that [l, r] is not extendable.
	//maxr is max r such that [l, r] is not extendable.
	build(1, 1, n + 1);
	build3(1, 1, n + 1);
	for (int i = 1; i <= n; i++)
		minl[i] = ask(canl[i] + 1, i), maxr[i] = ask2(i, canr[i] - 1);
	//[L --> R] is not reachable iff minimum of minl in range [L, R) <= L.
	memset(seg, 0, sizeof seg);
	memset(seg2, 0, sizeof seg2);
	build2(1, 1, n + 1);
	build4(1, 1, n + 1);
	cin >> q;
	while(q--)
	{
		int L, R;
		cin >> L >> R;
		if(L <= R)
			cout << (get2(1, 1, n + 1, L, R) <= L ? "NO" : "YES") << "\n";
		else
			cout << (get4(1, 1, n + 1, R + 1, L + 1) >= L ? "NO" : "YES") << "\n";
	}
}

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