Submission #122182

#	Time	Username	Problem	Language	Result	Execution time	Memory
122182		cerberus	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3027 ms	22524 KiB

long_mansion

/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 5e5 + 10, LOG = log2(N) + 5;

int c[N], l[N], r[N], lkey[N], rkey[N];
vector<int> pos[N];

int main() {
	fast_cin();
	int n; cin >> n;
	for (int i = 1; i <= n - 1; ++i) {
		cin >> c[i];
	}
	for (int i = 1; i <= n; ++i) {
		int b; cin >> b;
		for (int j = 0; j < b; ++j) {
			int k; cin >> k;
			pos[k].pb(i);
		}
	}
	for (int i = 1; i <= n; ++i) {
		pos[i].pb(0);
		pos[i].pb(n + 1);
		sort(pos[i].begin(), pos[i].end());
	}
	for (int i = 1; i <= n - 1; ++i) {
		auto it = lower_bound(pos[c[i]].begin(), pos[c[i]].end(), i + 1);
		rkey[i] = *it;
		lkey[i] = *(it - 1);
	}
	for (int i = 1; i <= n; ++i) {
		l[i] = r[i] = i;
		while (true) {
			if (l[i] > 1 and rkey[l[i] - 1] <= r[i]) {
				--l[i];
			} else if (r[i] < n and lkey[r[i]] >= l[i]) {
				++r[i];
			} else {
				break;
			}
		}
	}
	int q; cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		if (l[x] <= y and y <= r[x]) {
			cout << "YES\n";
		} else {
			cout << "NO\n";
		}
	}
}

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