Submission #411671

#	Time	Username	Problem	Language	Result	Execution time	Memory
411671		rqi	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	620 ms	101588 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

#define pb push_back
#define ins insert
#define lb lower_bound
#define bk back()

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

const int mx = 500005;
int N;
int C[mx];
vi A[mx];
vi key_poses[mx];
int l_edge[mx];
int r_edge[mx];

int l_ans[mx]; //left door
int r_ans[mx];
vi lends[mx];

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> N;
	for(int i = 1; i <= N-1; i++){
		cin >> C[i];
	}
	for(int i = 1; i <= N; i++){
		int B;
		cin >> B;
		for(int j = 0; j < B; j++){
			int A_val;
			cin >> A_val;
			A[i].pb(A_val);
		}
	}

	for(int i = 0; i <= N; i++){
		key_poses[i].pb(0);
	}
	for(int i = 1; i <= N; i++){
		for(auto u: A[i]){
			key_poses[u].pb(i);
		}
	}
	for(int i = 0; i <= N; i++){
		key_poses[i].pb(N+1);
	}

	

	for(int i = 0; i <= N; i++){
		// if(i == 0 || i == N){
		// 	l_edge[i] = 0;
		// 	r_edge[i] = N+1;
		// 	continue;
		// }
		int ind_r = upper_bound(all(key_poses[C[i]]), i)-key_poses[C[i]].begin();
		int ind_l = ind_r-1;
		l_edge[i] = key_poses[C[i]][ind_l];
		r_edge[i] = key_poses[C[i]][ind_r];
	}

	for(int i = 0; i <= N; i++){
		lends[l_edge[i]].pb(i);
	}

	// for(int i = 0; i <= N; i++){
	// 	cout << i << " " << l_edge[i] << " " << r_edge[i] << "\n";
	// }

	vi unanswered;
	set<int> eds;
	for(int i = N-1; i >= 0; i--){
		//cout << "i: " << i << "\n";
		unanswered.pb(i+1);
		eds.ins(i+1);
		for(auto u: lends[i+1]){
			assert(eds.count(u));
			eds.erase(u);
			//cout << "erase: " << u << "\n";
		}

		// cout << "eds:" << "\n";
		// for(auto u: eds){
		// 	cout << u << " ";
		// }
		// cout << "\n";

		while(sz(unanswered)){
			int q = unanswered.bk;
			auto it = eds.lb(q);
			if(it == eds.end()){
				break;
			}
			int r_pos = *it;
			if(r_pos >= r_edge[i]) break;
			l_ans[q] = i;
			r_ans[q] = r_pos;
			unanswered.pop_back();
		}
	}
	assert(sz(unanswered) == 0);

	// for(int i = 1; i <= N; i++){
	// 	cout << "i, l_ans[i], rans[i]: " << i << " " << l_ans[i] << " " << r_ans[i] << "\n";
	// }

	int Q;
	cin >> Q;
	for(int i = 1; i <= Q; i++){
		int X, Y;
		cin >> X >> Y;
		if(l_ans[X]+1 <= Y && Y <= r_ans[X]){
			cout << "YES" << "\n";
		}
		else{
			cout << "NO" << "\n";
		}
	}

}

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