Submission #1234934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234934		siewjh	Long Mansion (JOI17_long_mansion)	C++20	25 / 100	278 ms	128924 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int nums, lg[MAXN], typ[MAXN], lk[18][MAXN], rk[18][MAXN], lf[18][MAXN], rf[18][MAXN];
vector<int> vpos[MAXN];
void init(int (&spt)[18][MAXN], bool typ){
	for (int k = 1; k <= 18; k++)
		for (int i = nums - (1 << k); i >= 0; i--){
			if (typ) spt[k][i] = max(spt[k - 1][i], spt[k - 1][i + (1 << (k - 1))]);
			else spt[k][i] = min(spt[k - 1][i], spt[k - 1][i + (1 << (k - 1))]);
		}
}
int query(int (&spt)[18][MAXN], int l, int r, bool typ){
	int lgv = lg[r - l + 1];
	if (typ) return max(spt[lgv][l], spt[lgv][r + 1 - (1 << lgv)]);
	else return min(spt[lgv][l], spt[lgv][r + 1 - (1 << lgv)]);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> nums;
	lg[1] = 0;
	for (int i = 2; i <= nums; i++) lg[i] = lg[i >> 1] + 1;
	for (int i = 1; i < nums; i++) cin >> typ[i];
	for (int i = 1; i <= nums; i++){
		int knum; cin >> knum;
		for (int j = 0; j < knum; j++){
			int x; cin >> x;
			vpos[x].push_back(i);
		}
	}
	for (int i = 1; i < nums; i++){
		int t = typ[i];
		auto nit = lower_bound(vpos[t].begin(), vpos[t].end(), i + 1);
		auto pit = nit - 1;
		lk[0][i] = (nit == vpos[t].begin() ? 0 : *pit);
		rk[0][i] = (nit == vpos[t].end() ? nums + 1 : *nit);
	}
	init(lk, 0); init(rk, 1);
	for (int i = 1; i < nums; i++){
		int lkl = lk[0][i], rkl = rk[0][i];
		if (lkl == 0) lf[0][i] = 0;
		else{
			int lo = lkl, hi = i - 1, res = nums + 1;
			while (lo <= hi){
				int m = (lo + hi) >> 1;
				if (query(rk, lkl, m, 1) >= i + 1){
					res = m; hi = m - 1;
				}
				else lo = m + 1;
			}
			lf[0][i] = res;
		}
		if (rkl == nums + 1) rf[0][i] = nums;
		else{
			int lo = i + 1, hi = rkl - 1, res = 0;
			while (lo <= hi){
				int m = (lo + hi) >> 1;
				if (query(lk, m, rkl - 1, 0) <= i){
					res = m; lo = m + 1;
				}
				else hi = m - 1;
			}
			rf[0][i] = res;
		}
	}
	init(lf, 0); init(rf, 1);
	int queries; cin >> queries;
	while (queries--){
		int s, e; cin >> s >> e;
		if (s < e) cout << (query(lf, s, e - 1, 0) < s ? "NO" : "YES");
		else cout << (query(rf, e, s - 1, 1) >= s ? "NO" : "YES");
		cout << '\n';
	}
}

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