답안 #55107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55107	2018-07-06T05:10:42 Z	spencercompton	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	2180 ms	233316 KB

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

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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	760 KB	Output is correct
2	Correct	17 ms	1256 KB	Output is correct
3	Correct	15 ms	1676 KB	Output is correct
4	Correct	12 ms	1676 KB	Output is correct
5	Correct	12 ms	1676 KB	Output is correct
6	Correct	12 ms	1676 KB	Output is correct
7	Correct	16 ms	1676 KB	Output is correct

Subtask #2

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	760 KB	Output is correct
2	Correct	17 ms	1256 KB	Output is correct
3	Correct	15 ms	1676 KB	Output is correct
4	Correct	12 ms	1676 KB	Output is correct
5	Correct	12 ms	1676 KB	Output is correct
6	Correct	12 ms	1676 KB	Output is correct
7	Correct	16 ms	1676 KB	Output is correct
8	Correct	967 ms	11124 KB	Output is correct
9	Correct	931 ms	11124 KB	Output is correct
10	Correct	823 ms	12196 KB	Output is correct
11	Correct	938 ms	12564 KB	Output is correct
12	Correct	893 ms	12564 KB	Output is correct
13	Correct	812 ms	12940 KB	Output is correct
14	Correct	875 ms	12940 KB	Output is correct
15	Correct	848 ms	12940 KB	Output is correct
16	Correct	887 ms	12940 KB	Output is correct
17	Correct	929 ms	13108 KB	Output is correct
18	Correct	822 ms	13108 KB	Output is correct
19	Correct	827 ms	13108 KB	Output is correct
20	Correct	789 ms	13108 KB	Output is correct
21	Correct	885 ms	13108 KB	Output is correct
22	Correct	938 ms	13108 KB	Output is correct
23	Correct	936 ms	13108 KB	Output is correct
24	Correct	892 ms	13108 KB	Output is correct
25	Correct	869 ms	13108 KB	Output is correct
26	Correct	823 ms	13108 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1153 ms	29444 KB	Output is correct
2	Correct	1163 ms	29444 KB	Output is correct
3	Correct	1132 ms	29536 KB	Output is correct
4	Correct	1326 ms	29536 KB	Output is correct
5	Correct	1336 ms	29536 KB	Output is correct
6	Correct	1213 ms	29536 KB	Output is correct
7	Correct	1124 ms	29536 KB	Output is correct
8	Correct	883 ms	29536 KB	Output is correct
9	Correct	885 ms	29536 KB	Output is correct
10	Correct	1020 ms	29536 KB	Output is correct
11	Correct	896 ms	29536 KB	Output is correct

Subtask #4

75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	760 KB	Output is correct
2	Correct	17 ms	1256 KB	Output is correct
3	Correct	15 ms	1676 KB	Output is correct
4	Correct	12 ms	1676 KB	Output is correct
5	Correct	12 ms	1676 KB	Output is correct
6	Correct	12 ms	1676 KB	Output is correct
7	Correct	16 ms	1676 KB	Output is correct
8	Correct	967 ms	11124 KB	Output is correct
9	Correct	931 ms	11124 KB	Output is correct
10	Correct	823 ms	12196 KB	Output is correct
11	Correct	938 ms	12564 KB	Output is correct
12	Correct	893 ms	12564 KB	Output is correct
13	Correct	812 ms	12940 KB	Output is correct
14	Correct	875 ms	12940 KB	Output is correct
15	Correct	848 ms	12940 KB	Output is correct
16	Correct	887 ms	12940 KB	Output is correct
17	Correct	929 ms	13108 KB	Output is correct
18	Correct	822 ms	13108 KB	Output is correct
19	Correct	827 ms	13108 KB	Output is correct
20	Correct	789 ms	13108 KB	Output is correct
21	Correct	885 ms	13108 KB	Output is correct
22	Correct	938 ms	13108 KB	Output is correct
23	Correct	936 ms	13108 KB	Output is correct
24	Correct	892 ms	13108 KB	Output is correct
25	Correct	869 ms	13108 KB	Output is correct
26	Correct	823 ms	13108 KB	Output is correct
27	Correct	1153 ms	29444 KB	Output is correct
28	Correct	1163 ms	29444 KB	Output is correct
29	Correct	1132 ms	29536 KB	Output is correct
30	Correct	1326 ms	29536 KB	Output is correct
31	Correct	1336 ms	29536 KB	Output is correct
32	Correct	1213 ms	29536 KB	Output is correct
33	Correct	1124 ms	29536 KB	Output is correct
34	Correct	883 ms	29536 KB	Output is correct
35	Correct	885 ms	29536 KB	Output is correct
36	Correct	1020 ms	29536 KB	Output is correct
37	Correct	896 ms	29536 KB	Output is correct
38	Correct	1875 ms	77324 KB	Output is correct
39	Correct	2009 ms	104572 KB	Output is correct
40	Correct	1720 ms	104572 KB	Output is correct
41	Correct	1559 ms	125940 KB	Output is correct
42	Correct	1253 ms	125940 KB	Output is correct
43	Correct	1064 ms	125940 KB	Output is correct
44	Correct	1249 ms	125940 KB	Output is correct
45	Correct	1178 ms	125940 KB	Output is correct
46	Correct	1429 ms	125940 KB	Output is correct
47	Correct	1093 ms	125940 KB	Output is correct
48	Correct	992 ms	125940 KB	Output is correct
49	Correct	1266 ms	143704 KB	Output is correct
50	Correct	1907 ms	153344 KB	Output is correct
51	Correct	2180 ms	164236 KB	Output is correct
52	Correct	1286 ms	176696 KB	Output is correct
53	Correct	1680 ms	203828 KB	Output is correct
54	Correct	1584 ms	233316 KB	Output is correct
55	Correct	1513 ms	233316 KB	Output is correct