Submission #926336

#	Time	Username	Problem	Language	Result	Execution time	Memory
926336		amirhoseinfar1385	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	189 ms	108372 KiB

long_mansion

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int n,c[maxn],last[maxn],l[maxn],r[maxn],dpl[maxn],dpr[maxn];
vector<int>all[maxn],insl[maxn],dell[maxn],insr[maxn],delr[maxn],ins[maxn],del[maxn];

void vorod(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		cin>>c[i];
	}
	for(int i=1;i<=n;i++){
		int d;
		cin>>d;
		all[i].resize(d);
		for(int j=0;j<d;j++){
			cin>>all[i][j];
		}
	}
}

void pre(){
	for(int i=1;i<n;i++){
		for(auto x:all[i]){
			last[x]=i;
		}
		l[i]=last[c[i]];
	}
	for(int i=1;i<=n;i++){
		last[i]=n+3;
	}
	r[1]=n+3;
	for(int i=n;i>=2;i--){
		for(auto x:all[i]){
			last[x]=i;
		}
		r[i]=last[c[i-1]];
	}
	set<int>st;
	st.insert(n+1);
	insl[1].push_back(1);
	for(int i=n;i>=2;i--){
		if(i==n||l[i]!=i)
			st.insert(i);
		for(auto x:del[i]){
			st.erase(x);
		}
		if((*st.begin())>=r[i]){
			continue;
		}
		insl[i].push_back(i);
		auto y=st.lower_bound(r[i]);
		y--;
		auto x=*y;
		dell[x].push_back(i);
		del[l[i]].push_back(i);
	//	st.insert(i);
	}
	st.clear();
	for(int i=0;i<=n;i++){
		del[i].clear();
	}
	st.insert(0);
	insr[n].push_back(n);
	for(int i=1;i<n;i++){
		if(i==n||r[i]!=i)
			st.insert(i);
		for(auto x:del[i]){
			st.erase(x);
		}
		if((*st.rbegin())<=l[i]){
			continue;
		}
		insr[i].push_back(i);
		auto y=st.upper_bound(l[i]);
		auto x=*y;
		delr[x].push_back(i);
		del[r[i]].push_back(i);
	//	st.insert(i);
	}
	st.clear();
	for(int i=1;i<=n;i++){
		for(auto x:insl[i]){
			st.insert(x);
		}
		for(auto x:dell[i]){
			st.erase(x);
		}
		dpl[i]=(*st.rbegin());
	}
	st.clear();
	for(int i=n;i>=1;i--){
		for(auto x:insr[i]){
			st.insert(x);
		}
		for(auto x:delr[i]){
			st.erase(x);
		}
		dpr[i]=(*st.begin());
	}
}

void debug(){
	for(int i=1;i<=n;i++){
		cout<<i<<" "<<dpl[i]<<" "<<dpr[i]<<" "<<l[i]<<" "<<r[i]<<"\n";
	}
}

void solve(){
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		if(r>=dpl[l]&&r<=dpr[l]){
			cout<<"YES\n";
		}
		else{
			cout<<"NO\n";
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();
	pre();
//	debug();
	solve();
}

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