Submission #55101

#	Time	Username	Problem	Language	Result	Execution time	Memory
55101		spencercompton	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	2698 ms	263168 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
class Node{
	public:
		int s, e, maxi;
		Node *l, *r;
		Node (int st, int en){
			l = NULL;
			r = NULL;
			s = st;
			e = en;
			if(s!=e){
				l = new Node(s,(s+e)/2);
				r = new Node((s+e)/2+1,e);
			}
			maxi = 0;
		}
		int first (int bound){
			if(s==e){
				if(maxi>bound){
					return s;
				}
				return 99999999;
			}
			if(l->maxi >bound){
				return l->first(bound);
			}
			return r->first(bound);
		}
		int getmaxi(int st, int en){
			if(st<=s && e<=en){
				return maxi;
			}
			int ret = -1;
			if(st<=(s+e)/2){
				ret = max(ret,l->getmaxi(st,en));
			}
			if(en>(s+e)/2){
				ret = max(ret,r->getmaxi(st,en));
			}
			return ret;
		}
		void sett(int ind, int val){
			if(s==e){
				maxi = val;
			}
			else{
				if(ind<=(s+e)/2){
					l->sett(ind,val);
				}
				else{
					r->sett(ind,val);
				}
				maxi = max(l->maxi,r->maxi);
			}
		}
};
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));
		}
	}
	Node *t = new Node(0,n-1);
	for(int i = 0; i<n; i++){
		t->sett(i,right[i]);
	}
	//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 = t->getmaxi(to,possible[possible.size()-1]-1);
			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++){
		t->sett(i,right[i]);
	}
	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 = t->getmaxi(to,possible[possible.size()-1]-1);
			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:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<keys[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:108:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<keys[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:166:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<qbef[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:170:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<possible.size(); i++){
                 ~^~~~~~~~~~~~~~~~
long_mansion.cpp:190: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:205: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:213:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<qaft[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:244:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<qbef[i].size(); j++){
                  ~^~~~~~~~~~~~~~~
long_mansion.cpp:137:7: warning: argument 1 range [18446744071562067968, 18446744073709551615] exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=]
  bool inli[n];
       ^~~~
long_mansion.cpp:137: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: 0 / 75