Submission #916827

#	Time	Username	Problem	Language	Result	Execution time	Memory
916827		happypotato	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	3094 ms	143208 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 5e5 + 1;
const int MAX = 1e9, MIN = -1e9;
pii sp[mxN][20];
pii a[mxN];
int corr[mxN];
vector<int> keys[mxN];
int n;
int flog2(int x) {
	return 31 - __builtin_clz(x);
}
void build() {
	for (int i = 1; i <= n; i++) {
		sp[i][0] = a[i];
	}
	for (int bit = 1; bit < 20; bit++) {
		for (int i = 1; i + (1 << bit) - 1 <= n; i++) {
			sp[i][bit].ff = min(sp[i][bit - 1].ff, sp[i + (1 << (bit - 1))][bit - 1].ff);
			sp[i][bit].ss = max(sp[i][bit - 1].ss, sp[i + (1 << (bit - 1))][bit - 1].ss);
		}
	}
}
int querymin(int l, int r) {
	int bit = flog2(r - l + 1);
	return min(sp[l][bit].ff, sp[r - (1 << bit) + 1][bit].ff);
}
int querymax(int l, int r) {
	int bit = flog2(r - l + 1);
	return max(sp[l][bit].ss, sp[r - (1 << bit) + 1][bit].ss);
}
map<int, bool> sto;
bool recur(int x, int y) {
	// cout << x << ' ' << y << endl;
	if (sto.find(y) != sto.end()) return sto[y];
	sto[y] = false;
	if (x < y) {
		int req = querymin(x + 1, y);
		if (x <= req) { sto.erase(y); return true; }
		if (req == MIN) { sto.erase(y); return false; }
		return sto[y] = recur(x, req);
	} else if (x > y) {
		int req = querymax(y, x - 1);
		if (req <= x) { sto.erase(y); return true; }
		if (req == MAX) { sto.erase(y); return false; }
		return sto[y] = recur(x, req);
	} else return true;
}
int occur[mxN];
vector<int> qfreq[mxN];
void solve() {
	cin >> n;
	for (int i = 1; i < n; i++) cin >> corr[i];
	for (int i = 1; i <= n; i++) {
		int sz; cin >> sz;
		keys[i].resize(sz);
		for (int &x : keys[i]) cin >> x;
	}
 
	// sweep from left to right, take min of max
	for (int i = 1; i <= n; i++) occur[i] = MIN;
	a[1].ff = MIN;
	for (int i = 1; i < n; i++) {
		for (int x : keys[i]) occur[x] = i;
		a[i + 1].ff = occur[corr[i]];
	}
	// sweep from right to left, take max of min
	for (int i = 1; i <= n; i++) occur[i] = MAX;
	a[n].ss = MAX;
	for (int i = n; i > 1; i--) {
		for (int x : keys[i]) occur[x] = i;
		a[i - 1].ss = occur[corr[i - 1]];
	}
 
	// for (int i = 1; i <= n; i++) {
	// 	cout << i << ": " << a[i].ff << ' ' << a[i].ss << endl;
	// }
	build();
 
	int q; cin >> q;
	vector<pair<pii, bool>> queries(q);
	for (int i = 0; i < q; i++) {
		cin >> queries[i].ff.ff >> queries[i].ff.ss;
		qfreq[queries[i].ff.ff].pb(i);
	}
	for (int i = 1; i <= n; i++) {
		sto.clear();
		for (int ptr : qfreq[i]) {
			queries[ptr].ss = recur(queries[ptr].ff.ff, queries[ptr].ff.ss);
		}
	}
	for (int i = 0; i < q; i++) cout << (queries[i].ss ? "YES\n" : "NO\n");
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
}

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