oj.uz

Submission #55101

# Submission time Handle Problem Language Result Execution time Memory
55101 2018-07-06T04:58:27 Z spencercompton Long Mansion (JOI17_long_mansion) C++17
25 / 100
 2698 ms 263168 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 888 KB Output is correct
2 Correct 19 ms 1328 KB Output is correct
3 Correct 19 ms 2008 KB Output is correct
4 Correct 16 ms 2008 KB Output is correct
5 Correct 18 ms 2008 KB Output is correct
6 Correct 19 ms 2008 KB Output is correct
7 Correct 17 ms 2008 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 888 KB Output is correct
2 Correct 19 ms 1328 KB Output is correct
3 Correct 19 ms 2008 KB Output is correct
4 Correct 16 ms 2008 KB Output is correct
5 Correct 18 ms 2008 KB Output is correct
6 Correct 19 ms 2008 KB Output is correct
7 Correct 17 ms 2008 KB Output is correct
8 Correct 1081 ms 15700 KB Output is correct
9 Correct 965 ms 19700 KB Output is correct
10 Correct 1020 ms 25540 KB Output is correct
11 Correct 1143 ms 30448 KB Output is correct
12 Correct 810 ms 32732 KB Output is correct
13 Correct 818 ms 39200 KB Output is correct
14 Correct 845 ms 43248 KB Output is correct
15 Correct 904 ms 47076 KB Output is correct
16 Correct 929 ms 48412 KB Output is correct
17 Correct 949 ms 56360 KB Output is correct
18 Correct 1002 ms 60176 KB Output is correct
19 Correct 831 ms 64612 KB Output is correct
20 Correct 874 ms 67008 KB Output is correct
21 Correct 877 ms 69680 KB Output is correct
22 Correct 834 ms 77104 KB Output is correct
23 Correct 834 ms 80140 KB Output is correct
24 Correct 950 ms 84536 KB Output is correct
25 Correct 970 ms 88752 KB Output is correct
26 Correct 829 ms 93244 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1188 ms 117752 KB Output is correct
2 Correct 1289 ms 124876 KB Output is correct
3 Correct 1271 ms 131972 KB Output is correct
4 Correct 1103 ms 139280 KB Output is correct
5 Correct 1146 ms 146548 KB Output is correct
6 Correct 1085 ms 150960 KB Output is correct
7 Correct 934 ms 154704 KB Output is correct
8 Correct 889 ms 160448 KB Output is correct
9 Correct 922 ms 166644 KB Output is correct
10 Correct 903 ms 172632 KB Output is correct
11 Correct 1146 ms 178544 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 888 KB Output is correct
2 Correct 19 ms 1328 KB Output is correct
3 Correct 19 ms 2008 KB Output is correct
4 Correct 16 ms 2008 KB Output is correct
5 Correct 18 ms 2008 KB Output is correct
6 Correct 19 ms 2008 KB Output is correct
7 Correct 17 ms 2008 KB Output is correct
8 Correct 1081 ms 15700 KB Output is correct
9 Correct 965 ms 19700 KB Output is correct
10 Correct 1020 ms 25540 KB Output is correct
11 Correct 1143 ms 30448 KB Output is correct
12 Correct 810 ms 32732 KB Output is correct
13 Correct 818 ms 39200 KB Output is correct
14 Correct 845 ms 43248 KB Output is correct
15 Correct 904 ms 47076 KB Output is correct
16 Correct 929 ms 48412 KB Output is correct
17 Correct 949 ms 56360 KB Output is correct
18 Correct 1002 ms 60176 KB Output is correct
19 Correct 831 ms 64612 KB Output is correct
20 Correct 874 ms 67008 KB Output is correct
21 Correct 877 ms 69680 KB Output is correct
22 Correct 834 ms 77104 KB Output is correct
23 Correct 834 ms 80140 KB Output is correct
24 Correct 950 ms 84536 KB Output is correct
25 Correct 970 ms 88752 KB Output is correct
26 Correct 829 ms 93244 KB Output is correct
27 Correct 1188 ms 117752 KB Output is correct
28 Correct 1289 ms 124876 KB Output is correct
29 Correct 1271 ms 131972 KB Output is correct
30 Correct 1103 ms 139280 KB Output is correct
31 Correct 1146 ms 146548 KB Output is correct
32 Correct 1085 ms 150960 KB Output is correct
33 Correct 934 ms 154704 KB Output is correct
34 Correct 889 ms 160448 KB Output is correct
35 Correct 922 ms 166644 KB Output is correct
36 Correct 903 ms 172632 KB Output is correct
37 Correct 1146 ms 178544 KB Output is correct
38 Runtime error 2698 ms 263168 KB Memory limit exceeded 263168 {'time-wall': '2.784', 'max-rss': '103928', 'csw-forced': '227', 'cg-mem': '263168', 'time': '2.698', 'csw-voluntary': '7'} 262144
39 Halted 0 ms 0 KB -