Submission #122184

#	Time	Username	Problem	Language	Result	Execution time	Memory
122184		cerberus	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1028 ms	161380 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], lkey[N], rkey[N], lg2[N];
int lmost[N], lmost_table[N][LOG];
int rmost[N], rmost_table[N][LOG];
vector<int> pos[N];

void build_table(int *a, int table[N][LOG], int n, int f(int, int));
int query(int table[N][LOG], int l, int r, int f(int, int));
int my_min(int x, int y);
int my_max(int x, int y);

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);
	}
	rkey[0] = n + 1;
	lkey[n] = 0;
	set<pii> s;
	for (int i = 1; i <= n - 1; ++i) {
		s.insert({i - 1, rkey[i - 1]});
		int p = lkey[i];
		lmost[i] = i;
		while (true) {
			auto it = s.lower_bound({p, 0});
			if (it == s.end()) {
				break;
			} else if (it->second < i + 1) {
				s.erase(it);
			} else {
				lmost[i] = it->first;
				break;
			}
		}
	}
	s.clear();
	for (int i = n - 1; i >= 1; --i) {
		s.insert({i + 1, lkey[i + 1]});
		int p = rkey[i];
		rmost[i] = i;
		while (true) {
			auto it = s.lower_bound({p, 0});
			if (it == s.begin()) {
				break;
			}
			--it;
			if (it->second > i) {
				s.erase(it);
			} else {
				rmost[i] = it->first;
				break;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		lg2[i] = lg2[i - 1];
		while (1 << (lg2[i] + 1) <= i) {
			++lg2[i];
		}
	}
	build_table(lmost, lmost_table, n - 1, my_min);
	build_table(rmost, rmost_table, n - 1, my_max);
	int q; cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		if (x < y) {
			if (query(lmost_table, x, y - 1, my_min) < x) {
				cout << "NO\n";
			} else {
				cout << "YES\n";
			}
		} else {
			if (query(rmost_table, y, x - 1, my_max) >= x) {
				cout << "NO\n";
			} else {
				cout << "YES\n";
			}
		}
	}
}

void build_table(int *a, int table[N][LOG], int n, int f(int, int)) {
	for (int i = n; i >= 1; --i) {
		table[i][0] = a[i];
		for (int j = 1; i + (1 << j) - 1 <= n; ++j) {
			table[i][j] = f(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int query(int table[N][LOG], int l, int r, int f(int, int)) {
	int j = lg2[r - l + 1];
	return f(table[l][j], table[r - (1 << j) + 1][j]);
}

int my_min(int x, int y) {
	return min(x, y);
}

int my_max(int x, int y) {
	return max(x, y);
}

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