Submission #511259

#	Time	Username	Problem	Language	Result	Execution time	Memory
511259		ArianKheirandish	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	316 ms	68956 KiB

long_mansion

// in the name of God//
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x)    cerr << #x << " = " << x << endl;
const int maxn = 5e5 + 10;
int n, q;
vector<int> a[maxn], keys[maxn];
int b[maxn], c[maxn];
int dpL[maxn], dpR[maxn];

bool check(int l, int r, int x){
	int ind = lower_bound(keys[x].begin(),keys[x].end(), l) - keys[x].begin();
	if(ind < keys[x].size() && keys[x][ind] <= r)
		return 1;
	else
		return 0;
}

int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1 ; i < n ; i ++)
		cin >> c[i];
		
	for(int i = 1 ; i <= n ; i ++){
		cin >> b[i];
		for(int j = 0 ; j < b[i] ; j ++){
			int x;
			cin >> x;
			a[i].push_back(x);
		}
		for(auto x : a[i])
			keys[x].push_back(i);
	}
	
	for(int i = 1 ; i <= n ; i ++)
		dpL[i] = dpR[i] = i;
		
	for(int i = 1 ; i <= n ; i ++){
		while(1){
			if(dpL[i] > 1 && check(dpL[i], dpR[i], c[dpL[i] - 1]))
				dpR[i] = max(dpR[i], dpR[dpL[i] - 1]),
				dpL[i] = dpL[dpL[i] - 1];
		
			else if(dpR[i] < n && check(dpL[i], dpR[i], c[dpR[i]]))
				dpR[i] = dpR[i] + 1;
			
			else
				break;
		}
		
		//debug(i);
	}
	
	cin >> q;
	while(q --){
		int x, y;
		cin >> x >> y;
		cout << ((dpL[x] <= y && y <= dpR[x]) ? "YES" : "NO") << '\n';
	}
	return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'bool check(int, int, int)':
long_mansion.cpp:15:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  if(ind < keys[x].size() && keys[x][ind] <= r)
      |     ~~~~^~~~~~~~~~~~~~~~

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