Submission #448301

#	Time	Username	Problem	Language	Result	Execution time	Memory
448301		dutch	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	761 ms	60896 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 l, r;
	SegmentTree(int N, int* v) : a(S+S, INF) {
		for(int i=N-0; --i>=0; ) a[i+S-1] = v[i];
		for(int i=S-1; --i>=0; ){
			a[i] = min(a[2*i+1], a[2*i+2]);
		}
	}
	int query(int x, int lx, int rx){
		if(a[x] >= r || rx <= l) return 0;
		if(rx - lx < 2) return lx;
		int mx = (lx + rx) / 2;
		return query(2*x+1, lx, mx) ? : query(2*x+2, mx, rx);
	}
	int operator()(int L, int V){ //first v[i] s.t. i>=l && v[i]<v
		l = L, r = V; return query(0, 0, S);
	}
	int rangeMin(int x, int lx, int rx){
		if(r<=lx || rx<=l) return INF;
		if(l<=lx && rx<=r) return a[x];
		int mx = (lx + rx) / 2;
		return min(rangeMin(2*x+1, lx, mx), rangeMin(2*x+2, mx, rx));
	}
	int rangeMin(int L, int R){
		l = L, r = R + 1; return rangeMin(0, 0, S);
	}
};
 
int n, q, c[LIM], last[LIM], l[LIM], r[LIM], rL[LIM], rR[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=1; i<n; ++i){
		f(rL[i]), f(rR[i]);
	}
	swap(rL, rR);
	reverse(rL+1, rL+n);
	reverse(rR+1, rR+n);
	for(int i=0; i<q; ++i){
		for(int &j : b[i]) f(j);
	}
}

void calc(int* v){
	for(int i=1; i<n; ++i) r[i] =-r[i];
	SegmentTree st(n+1, r);
	for(int i=1; i<n; ++i) r[i] =-r[i];
	for(int i=1; i<n; ++i){
		v[i] = min(n, st(l[i], -i));
		if(!l[i]) v[i] = 0;
	}
}
 
void solve(){
	SegmentTree st(n, rR);
	
	for(int i=0; i<q; ++i){
		auto [u, v] = b[i];
		if(u > v) continue;
		ans[i] = st.rangeMin(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]) last[j] = i;
		l[i] = last[c[i]];
	}
	fill(last, last+n+1, n+1);
	for(int i=n; i>1; --i){
		for(int &j : a[i]) last[j] = i;
		r[i-1] = last[c[i-1]];
	}
	calc(rR);
	flip();
	calc(rR);
 
	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