Submission #1188839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188839		yellowtoad	Long Mansion (JOI17_long_mansion)	C++20	0 / 100	3097 ms	25524 KiB

long_mansion

#include <iostream>
#include <vector>
#define f first
#define s second
#define int long long
using namespace std;

int n, m, test, a[500010], ll[500010], rr[500010], lst[500010];
vector<int> v[500010];
vector<pair<int,int>> rng;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin >> m;
		for (int j = 0; j < m; j++) {
			int x;
			cin >> x;
			v[i].push_back(x);
		}
	}
	for (int i = 1; i <= n; i++) lst[i] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < v[i].size(); j++) lst[v[i][j]] = i;
		if (i != n) ll[i] = lst[a[i]];
	}
	ll[n] = 0;
	for (int i = 1; i <= n; i++) lst[i] = n+1;
	for (int i = n; i >= 1; i--) {
		if (i != n) rr[i] = lst[a[i]];
		for (int j = 0; j < v[i].size(); j++) lst[v[i][j]] = i;
	}
	rr[0] = n+1;
	for (int i = 1; i <= n; i++) {
		for (int j = i-1; j >= ll[i]; j--) {
			if (rr[j] > i) {
				rng.push_back({j+1,i});
				break;
			}
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = i; j < rr[i-1]; j++) {
			if (ll[j] < i) {
				rng.push_back({i,j});
				break;
			}
		}
	}
	cin >> test;
	while (test--) {
		int x, y;
		cin >> x >> y;
		for (int i = 0; i < rng.size(); i++) {
			if ((rng[i].f <= x) && (x <= rng[i].s)) {
				if (!((rng[i].f <= y) && (y <= rng[i].s))) {
					cout << "NO" << endl;
					goto skip;
				}
			}
		}
		cout << "YES" << endl;
		skip:;
	}
}

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