Submission #1236284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236284		gelastropod	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	1833 ms	209644 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct node1 {
	int s, e, m, v, lazy = INT_MAX;
	node1* l, * r;

	node1(int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(INT_MAX) {
		if (s != e)
			l = new node1(s, m),
			r = new node1(m + 1, e);
	}

	void prop() {
		if (s == e) return;
		if (lazy != INT_MAX) {
			l->lazy = min(l->lazy, lazy);
			r->lazy = min(r->lazy, lazy);
			l->v = min(l->v, lazy);
			r->v = min(r->v, lazy);
		}
	}

	void upd(int a, int b, int x) {
		if (b < s || a > e) return;
		if (a <= s && b >= e) {
			v = min(v, x);
			lazy = min(lazy, x);
			return;
		}
		prop();
		l->upd(a, b, x);
		r->upd(a, b, x);
		v = min(l->v, r->v);
	}

	int qry(int a) {
		if (s == e) return v;
		prop();
		if (a <= m) return l->qry(a);
		else return r->qry(a);
	}
} *root1;

struct node2 {
	int s, e, m, v, lazy = -1;
	node2* l, * r;

	node2(int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(-1) {
		if (s != e)
			l = new node2(s, m),
			r = new node2(m + 1, e);
	}

	void prop() {
		if (s == e) return;
		if (lazy != -1) {
			l->lazy = max(l->lazy, lazy);
			r->lazy = max(r->lazy, lazy);
			l->v = max(l->v, lazy);
			r->v = max(r->v, lazy);
		}
	}

	void upd(int a, int b, int x) {
		if (b < s || a > e) return;
		if (a <= s && b >= e) {
			v = max(v, x);
			lazy = max(lazy, x);
			return;
		}
		prop();
		l->upd(a, b, x);
		r->upd(a, b, x);
		v = max(l->v, r->v);
	}

	int qry(int a) {
		if (s == e) return v;
		prop();
		if (a <= m) return l->qry(a);
		else return r->qry(a);
	}
} *root2;

signed main() {
	int N, a, b, Q;
	cin >> N;
	vector<int> C, occur(N, -1);
	vector<vector<int>> vals(N, vector<int>());
	for (int i = 0; i < N - 1; i++) {
		cin >> a;
		a--;
		C.push_back(a);
	}
	for (int i = 0; i < N; i++) {
		cin >> a;
		for (int j = 0; j < a; j++) {
			cin >> b;
			b--;
			vals[i].push_back(b);
		}
	}
	root1 = new node1(0, N - 1);
	root2 = new node2(0, N - 1);
	set<int> indset;
	vector<int> rvals, lvalspzh(N - 1, 0);
	vector<pair<int, int>> lvals, rvalspzh;
	for (int i = 0; i < N - 1; i++) {
		for (int j : vals[i]) occur[j] = i;

		rvals.push_back(occur[C[i]]);
		rvalspzh.push_back(pair<int, int>(occur[C[i]], i));
	}
	occur = vector<int>(N, INT_MAX);
	for (int i = N - 2; i >= 0; i--) {
		for (int j : vals[i + 1]) occur[j] = i + 1;
		lvalspzh[i] = occur[C[i]];
		lvals.push_back(pair<int, int>(occur[C[i]], i));
	}
	sort(lvals.begin(), lvals.end(), greater<pair<int, int>>());
	sort(rvalspzh.begin(), rvalspzh.end());
	auto iter = rvalspzh.begin();
	while (iter != rvalspzh.end() && iter->first == -1) {
		indset.insert(iter->second + 1);
		iter++;
	}
	for (int i = 0; i < N - 1; i++) {
		while (iter != rvalspzh.end() && iter->first == i) {
			indset.insert(iter->second + 1);
			iter++;
		}
		if (lvalspzh[i] == INT_MAX) {
			root2->upd(i + 1, N, i);
			continue;
		}
		auto itero = indset.upper_bound(lvalspzh[i]);
		if (itero == indset.begin()) continue;
		itero--;
		if (*itero <= i) continue;
		root2->upd(i + 1, *itero - 1, i);
	}
	iter = lvals.begin();
	indset = set<int>();
	while (iter != lvals.end() && iter->first == INT_MAX) {
		indset.insert(iter->second);
		iter++;
	}
	for (int i = N - 1; i > 0; i--) {
		while (iter != lvals.end() && iter->first == i) {
			indset.insert(iter->second);
			iter++;
		}
		if (rvals[i - 1] == -1) {
			root1->upd(0, i - 1, i);
			continue;
		}
		auto itero = indset.lower_bound(rvals[i - 1]);
		if (itero == indset.end() || *itero >= i) continue;
		root1->upd(*itero + 1, i - 1, i);
	}
	/*for (int i = 0; i < N; i++) cout << root1->qry(i) << ' ';
	cout << '\n';
	for (int i = 0; i < N; i++) cout << root2->qry(i) << ' ';
	cout << '\n';*/
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		cin >> a >> b;
		a--, b--;
		if (b >= root1->qry(a) || b <= root2->qry(a)) cout << "NO\n";
		else cout << "YES\n";
	}
}

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