Submission #55107

#	Time	Username	Problem	Language	Result	Execution time	Memory
55107		spencercompton	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	2180 ms	233316 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
int maxi[1048576];
int l[1048576];
int r[1048576];
int point = 0;
int create(int st, int en){
	int now = point++;
	l[now] = -1;
	r[now] = -1;
	maxi[now] = 0;
	if(st!=en){
		int lv = create(st,(st+en)/2);
		l[now] = lv;
		int rv = create((st+en)/2+1,en);
		r[now] = rv;
	}
	return now;
}
int getmaxi(int st, int en, int s, int e, int now){
	if(st<=s && e<=en){
		return maxi[now];
	}
	int ret = -1;
	if(st<=(s+e)/2){
		ret = max(ret,getmaxi(st,en,s,(s+e)/2,l[now]));
	}
	if(en>(s+e)/2){
		ret = max(ret,getmaxi(st,en,(s+e)/2+1,e,r[now]));
	}
	return ret;
}
void sett(int ind, int val, int s, int e, int now){
	if(s==e){
		maxi[now] = val;
	}
	else{
		if(ind<=(s+e)/2){
			sett(ind,val,s,(s+e)/2,l[now]);
		}
		else{
			sett(ind,val,(s+e)/2+1,e,r[now]);
		}
		maxi[now] = max(maxi[l[now]],maxi[r[now]]);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int need[n];
	need[0] = 0;
	//need[i] is the lock on the left side of room i

	for(int i = 1; i<n; i++){
		cin >> need[i];
		need[i]--;
	}
	int last[n];
	int left[n];
	//how far left do you need to go to get a key that can open the lock to the left of this room
	
	vector<int> keys[n];
	for(int i = 0; i<n; i++){
		int len;
		cin >> len;
		for(int j =0 ; j<len; j++){
			int x;
			cin >> x;
			x--;
			keys[i].push_back(x);
		}
	}

	int right[n];
	//how far left do you need to go to get a key that can open the lock to the right of this room
	for(int i = 0; i<n; i++){
		last[i] = -1;
	}
	for(int i = 0; i<n; i++){
		left[i] = last[need[i]];
		for(int j = 0; j<keys[i].size(); j++){
			last[keys[i][j]] = i;
		}
	}
	for(int i = 0; i<n; i++){
		last[i] = n;
	}
	for(int i = n-1; i>=0; i--){
		if(i==n-1){
			right[i] = n;
		}
		else{
			right[i] = last[need[i+1]];
		}
		for(int j = 0; j<keys[i].size(); j++){
			last[keys[i][j]] = i;
		}
	}
	vector<pair<int, int> > qbef[n];
	//starting is before this
	vector<pair<int, int> > qaft[n];
	//starting is after this
	int q;
	cin >> q;
	int ans[q];
	for(int i = 0; i<q; i++){
		ans[i] = -1;
		int s, t;
		cin >> s >> t;
		s--;
		t--;
		if(s<t){
			qbef[t].push_back(make_pair(s,i));
		}
		else{
			qaft[t].push_back(make_pair(s,i));
		}
	}
	int t = create(0,n-1);
	for(int i = 0; i<n; i++){
		sett(i,right[i],0,n-1,t);
	}
	//going from left to right
	bool inli[n];
	for(int i = 0; i<n; i++){
		inli[i] = false;
	}
	vector<int> possible;
	possible.push_back(0);
	inli[0] = true;
	for(int i = 1; i<n; i++){
		while(possible.size()>0){
			int to = left[i];
			if(to>=possible[possible.size()-1]){
				break;
			}
			if(to<0){
				inli[possible[possible.size()-1]] = false;
				possible.pop_back();
				continue;
			}
			int maxi = getmaxi(to,possible[possible.size()-1]-1,0,n-1,t);
			if(maxi>=i){
				inli[possible[possible.size()-1]] = false;
				possible.pop_back();
			}
			else{
				break;
			}
		}
		possible.push_back(i);
		inli[i] = true;
		for(int j = 0; j<qbef[i].size(); j++){
			ans[qbef[i][j].second] = inli[qbef[i][j].first];
		}
	}
	for(int i = 0; i<possible.size(); i++){
		inli[possible[i]] = false;
	}
	possible.clear();

	//need[0] is 0, need[1] is need[n-1]
	int tmp[n];
	tmp[0] = 0;
	for(int i = 1; i<n; i++){
		tmp[i] = need[n-i];
	}
	for(int i = 0; i<n; i++){
		need[i] = tmp[i];
	}

	for(int i = 0; i<n; i++){
		last[i] = -1;
	}
	for(int i = 0; i<n; i++){
		left[i] = last[need[i]];
		for(int j = 0; j<keys[n-i-1].size(); j++){
			last[keys[n-i-1][j]] = i;
		}
	}

	for(int i = 0; i<n; i++){
		last[i] = n;
	}
	for(int i = n-1; i>=0; i--){
		if(i==n-1){
			right[i] = n;
		}
		else{
			right[i] = last[need[i+1]];
		}
		for(int j = 0; j<keys[n-i-1].size(); j++){
			last[keys[n-1-i][j]] = i;
		}
	}
	for(int i = 0; i<n; i++){
		qbef[i].clear();
	}
	for(int i = 0; i<n; i++){
		for(int j = 0; j<qaft[i].size(); j++){
			qbef[n-i-1].push_back(make_pair(n-qaft[i][j].first-1,qaft[i][j].second));
		}
	}
	for(int i = 0; i<n; i++){
		sett(i,right[i],0,n-1,t);
	}
	possible.push_back(0);
	inli[0] = true;
	for(int i = 1; i<n; i++){
		while(possible.size()>0){
			int to = left[i];
			if(to>=possible[possible.size()-1]){
				break;
			}
			if(to<0){
				inli[possible[possible.size()-1]] = false;
				possible.pop_back();
				continue;
			}
			int maxi = getmaxi(to,possible[possible.size()-1]-1,0,n-1,t);
			if(maxi>=i){
				inli[possible[possible.size()-1]] = false;
				possible.pop_back();
			}
			else{
				break;
			}
		}
		possible.push_back(i);
		inli[i] = true;
		for(int j = 0; j<qbef[i].size(); j++){
			ans[qbef[i][j].second] = inli[qbef[i][j].first];
		}
	}
	for(int i = 0; i<q; i++){
		cout << (ans[i]?"YES":"NO") << endl;
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<keys[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<keys[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:155:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<qbef[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:159:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<possible.size(); i++){
                 ~^~~~~~~~~~~~~~~~
long_mansion.cpp:179:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<keys[n-i-1].size(); j++){
                  ~^~~~~~~~~~~~~~~~~~~
long_mansion.cpp:194:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<keys[n-i-1].size(); j++){
                  ~^~~~~~~~~~~~~~~~~~~
long_mansion.cpp:202:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<qaft[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:233:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<qbef[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:126:7: warning: argument 1 range [18446744071562067968, 18446744073709551615] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
  bool inli[n];
       ^~~~
long_mansion.cpp:126:7: note: in a call to built-in allocation function 'void* __builtin_alloca_with_align(long unsigned int, long unsigned int)'

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