Submission #1235080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235080		gelastropod	Long Mansion (JOI17_long_mansion)	C++20	0 / 100	2925 ms	36952 KiB

long_mansion

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

struct node1 {
	int s, e, m, v;
	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 upd(int n, int x) {
		if (s == e) {
			v = x;
			return;
		}
		if (n <= m) l->upd(n, x);
		else r->upd(n, x);
		v = min(l->v, r->v);
	}

	int qry(int a, int b) {
		if (b < s || a > e) return INT_MAX;
		if (a <= s && b >= e) return v;
		return min(l->qry(a, b), r->qry(a, b));
	}
} *root1;

struct node2 {
	int s, e, m, v;
	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 upd(int n, int x) {
		if (s == e) {
			v = x;
			return;
		}
		if (n <= m) l->upd(n, x);
		else r->upd(n, x);
		v = max(l->v, r->v);
	}

	int qry(int a, int b) {
		if (b < s || a > e) return -1;
		if (a <= s && b >= e) return v;
		return max(l->qry(a, b), r->qry(a, b));
	}
} *root2;

signed main() {
	int N, a, b, Q;
	cin >> N;
	vector<int> C, occur(N, -1);
	vector<vector<int>> vals;
	for (int i = 0; i < N - 1; i++) {
		cin >> a;
		a--;
		C.push_back(a);
	}
	for (int i = 0; i < N; i++) {
		cin >> a;
		vals.push_back({});
		for (int j = 0; j < a; j++) {
			cin >> b;
			b--;
			vals.back().push_back(b);
		}
	}
	root1 = new node1(0, N - 1);
	root2 = new node2(0, N - 1);
	for (int i = 0; i < N - 1; i++) {
		for (int j : vals[i]) occur[j] = i;
		root1->upd(i, occur[C[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;
		root2->upd(i, occur[C[i]]);
	}
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		cin >> a >> b;
		a--, b--;
		if (a < b) {
			int low = 0, high = a, ans = a;
			while (low <= high) {
				int x = (low + high) / 2;
				if (a >= root2->qry(x, a - 1)) {
					high = x - 1;
					ans = x;
				}
				else low = x + 1;
			}
			if (ans <= root1->qry(a, b - 1)) cout << "YES\n";
			else cout << "NO\n";
		}
		else if (b < a) {
			int low = a, high = N - 1, ans = a;
			while (low <= high) {
				int x = (low + high) / 2;
				if (a <= root1->qry(a, x - 1)) {
					low = x + 1;
					ans = x;
				}
				else high = x - 1;
			}
			if (ans >= root2->qry(b, a - 1)) cout << "YES\n";
			else cout << "NO\n";
		}
		else cout << "YES\n";
	}
}

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