Submission #448308

#	Time	Username	Problem	Language	Result	Execution time	Memory
448308		dutch	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	560 ms	48812 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
#define f(z) z = n + 1 - z
 
const int LIM = 5e5+1, INF = 1e9, S = 1<<19;
 
struct SegmentTree{
	vector<int> a; int j, z;
	SegmentTree(int N, int* v) : a(S+S) {
		for(int i=N; --i>=0; ) a[i+S] = v[i];
		for(int i=S; --i; ){
			a[i] = max(a[2*i], a[2*i+1]);
		}
	}
	int rangeMax(int l, int r){
		int x = -INF;
		for(l+=S, r+=S+1; l<r; l/=2, r/=2){
			if(l & 1) x = max(x, a[l++]);
			if(r & 1) x = max(x, a[--r]);
		}
		return x;
	}
	int query(int x, int lx, int rx){
		if(a[x] <= z || rx <= j) return 0;
		if(rx - lx < 2) return lx;
		int mx = (lx + rx) / 2;
		return query(2*x, lx, mx) ? : query(2*x+1, mx, rx);
	}
	int operator()(int L, int V){ //first v[i] s.t. i>=l && v[i]>v
		j = L, z = V; return query(1, 0, S);
	}
};
 
int n, q, c[LIM], l[LIM], r[LIM], block[LIM];
array<int, 2> b[LIM];
bool ans[LIM];
vector<int> a[LIM];
 
void flip(){
	for(int i=1; i<n; ++i){
		f(l[i]), f(r[i]);
	}
	swap(l, r);
	reverse(l+1, l+n);
	reverse(r+1, r+n);
	for(int i=0; i<q; ++i){
		for(int &j : b[i]) f(j);
	}
}
 
void solve(){
	SegmentTree x(n, r);
	block[0] = 0;
	for(int i=1; i<n; ++i){
		block[i] = l[i] ? -min(n, x(l[i], i)) : 0;
	}
	SegmentTree y(n, block);
	
	for(int i=0; i<q; ++i){
		auto [u, v] = b[i];
		if(u < v) ans[i] = -y.rangeMax(u, v-1) >= u;
	}
}
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1; i<n; ++i) cin >> c[i];
	for(int i=1, j; i<=n; ++i){
		cin >> j;
		a[i].resize(j);
		for(int &k : a[i]) cin >> k;
	}
 
	cin >> q;
	for(int i=0; i<q; ++i){
		cin >> b[i][0] >> b[i][1];
	}
 
	for(int i=1; i<n; ++i){
		for(int &j : a[i]) block[j] = i;
		l[i] = block[c[i]];
	}
	fill(block, block+n+1, n+1);
	for(int i=n; i>1; --i){
		for(int &j : a[i]) block[j] = i;
		r[i-1] = block[c[i-1]];
	}
	solve();
	flip();
	solve();

	for(int i=0; i<q; ++i){
		cout << (ans[i] ? "YES" : "NO") << '\n';
	}
}

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