Submission #1234667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234667		emptypringlescan	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	595 ms	75000 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
int n;
int cor[500005];
vector<int> keys[500005];
pair<int,int> ans[500005];
vector<pair<int,int> > lw,rw;
void dnc(int l, int r, vector<pair<int,int> > lft, vector<pair<int,int> > rgt){ //only consider walls blocking [l,r]
	if(l>r) return;
	int m=(l+r)/2;
	vector<pair<int,int> > monol,monor;
	for(int i=0; i<(int)lft.size(); i++){
		if(lft[i].first>m) continue;
		monol.push_back(lft[i]);
	}
	for(int i=0; i<(int)rgt.size(); i++){
		if(rgt[i].second<m) continue;
		monor.push_back(rgt[i]);
	}
	int c1=0,c2=0;
	//cout << l << ':' << r << '\n';
	//for(auto i:monol) cout << i.first << 'l' << i.second << '\n';
	//for(auto i:monor) cout << i.first << 'r' << i.second << '\n';
	for(int i=m; i>=l; i--){
		while(true){
			if(c1>=(int)monol.size()||c2>=(int)monor.size()) break;
			if(monol[c1].first<=i&&monor[c2].first<=monol[c1].first&&monor[c2].second<=monol[c1].second) break;
			if(monol[c1].first>i) c1++;
			else if(monor[c2].first>monol[c1].first) c2++;
			else c1++;
		}
		//cout << i << ' ';
		if(c1<(int)monol.size()&&c2<(int)monor.size()){
			//cout << monol[c1].first << ' ' << monor[c2].second << '\n';
			ans[i].first=max(ans[i].first,monol[c1].first);
			ans[i].second=min(ans[i].second,monor[c2].second);
		}
	}
	c1=0,c2=0;
	for(int i=m; i<=r; i++){
		while(true){
			if(c1>=(int)monol.size()||c2>=(int)monor.size()) break;
			if(monor[c2].second>=i&&monol[c1].second>=monor[c2].second&&monol[c1].first>=monor[c2].first) break;
			if(monor[c2].second<i) c2++;
			else if(monol[c1].second<monor[c2].second) c1++;
			else c2++;
		}
		//cout << i << ' ';
		if(c1<(int)monol.size()&&c2<(int)monor.size()){
			//cout << monol[c1].first << ' ' << monor[c2].second << '\n';
			ans[i].first=max(ans[i].first,monol[c1].first);
			ans[i].second=min(ans[i].second,monor[c2].second);
		}
	}
	if(l!=r){
		vector<pair<int,int> > tmpl,tmpr;
		for(auto i:lft) if(i.first<m) tmpl.push_back(i);
		for(auto i:rgt) if(i.second<m) tmpr.push_back(i);
		dnc(l,m-1,tmpl,tmpr);
		tmpl.clear(); tmpr.clear();
		for(auto i:lft) if(i.first>m) tmpl.push_back(i);
		for(auto i:rgt) if(i.second>m) tmpr.push_back(i);
		dnc(m+1,r,tmpl,tmpr);
	}
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=1; i<n; i++) cin >> cor[i];
	for(int i=1; i<=n; i++){
		int m;
		cin >> m;
		for(int j=0; j<m; j++){
			int x;
			cin >> x;
			keys[i].push_back(x);
		}
	}
	int prev[n+5];
	memset(prev,0,sizeof(prev));
	for(int i=1; i<n; i++){
		for(int j:keys[i]) prev[j]=i;
		if(prev[cor[i]]!=i) rw.push_back({prev[cor[i]]+1,i});
	}
	rw.push_back({0,n});
	for(int i=0; i<=n; i++) prev[i]=n+1;
	for(int i=n; i>1; i--){
		for(int j:keys[i]) prev[j]=i;
		if(prev[cor[i-1]]!=i) lw.push_back({i,prev[cor[i-1]]-1});
	}
	lw.push_back({1,n+1});
	for(int i=1; i<=n; i++) ans[i]={1,n};
	dnc(1,n,lw,rw);
	//for(int i=1; i<=n; i++) cout << ans[i].first << ' ' << ans[i].second << '\n';
	int q;
	cin >> q;
	while(q--){
		int a,b;
		cin >> a >> b;
		if(b>=ans[a].first&&b<=ans[a].second) cout << "YES\n";
		else cout << "NO\n";
	}
}

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