Submission #539001

#	Time	Username	Problem	Language	Result	Execution time	Memory
539001		valerikk	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1033 ms	70824 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

const int N = 500500;

int n;
int c[N];
int b[N];
vector<int> a[N];
vector<int> inds[N];
int L[N], R[N];
int cnt[N];

bool check(int l, int r, int x) {
	auto it = lower_bound(inds[x].begin(), inds[x].end(), l);
	return it != inds[x].end() && *it <= r;
}

void rec(int l, int r) {
	if (l > r) {
		return;
	}

	int m = (l + r) / 2;
	rec(l, m - 1);
	rec(m + 1, r);

	vector<int> left;
	for (int i = m - 1; i >= l; --i) {
		if (R[i] == m - 1 && check(L[i], R[i], c[m - 1])) {
			left.push_back(i);
		}
	}

	vector<int> right;
	for (int i = m + 1; i <= r; ++i) {
		if (L[i] == m + 1 && check(L[i], R[i], c[m])) {
			right.push_back(i);
		}
	}

	vector<int> clr;
	
	auto add = [&](int i) {
		for (int x : a[i]) {
			++cnt[x];
			clr.push_back(x);
		}
	};

	auto clear = [&]() {
		for (int x : clr) {
			cnt[x] = 0;
		}
	};

	int tl = m, tr = m;
		
	auto go = [&]() {
		while (true) {
			if (tl > l && cnt[c[tl - 1]] > 0) {
				--tl;
				add(tl);
			} else if (tr < r && cnt[c[tr]] > 0) {
				++tr;
				add(tr);
			} else {
				break;
			}
		}
	};

	add(m);
	go();
	
	L[m] = tl;
	R[m] = tr;

	int last = m;
	for (int i : left) {
		for (int j = last - 1; j >= L[i]; --j) {
			add(j);
		}
		go();
		L[i] = tl;
		R[i] = tr;
		last = L[i];
	}

	clear();

	tl = m, tr = m;
	add(m);
	go();

	last = m;
	for (int i : right) {
		for (int j = last + 1; j <= R[i]; ++j) {
			add(j);
		}
		go();
		L[i] = tl;
		R[i] = tr;
		last = R[i];
	}

	clear();
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		cin >> c[i];
		--c[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
		for (int j = 0; j < b[i]; ++j) {
			int x;
			cin >> x;
			--x;
			a[i].push_back(x);
			inds[x].push_back(i);
		}
	}

	rec(0, n - 1);

	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		cout << (y >= L[x] && y <= R[x] ? "YES" : "NO") << "\n";
	}

	return 0;
}

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