Submission #412755

#	Time	Username	Problem	Language	Result	Execution time	Memory
412755		amoo_safar	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1760 ms	144640 KiB

long_mansion

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 5e5 + 10;
const ll Inf = 2242545357980376863LL;
const int Log = 20;

int n;
int L[Log][N], R[Log][N];
int C[N];

vector<int> B[N];

int vis[N];

typedef pair<int, int> pii;
map<pii, pii> mp;

pii Solve(pii A){
	// cerr << "^ " << A.F << ' ' << A.S << '\n';
	if(mp.count(A))
		return mp[A];
	int l = A.F, r = A.S;
	
	for(int lg = Log - 1; lg >= 0; lg --){
		if(l <= L[lg][r + 1])
			r += (1 << lg);
	}
	for(int lg = Log - 1; lg >= 0; lg --){
		if(l <= (1 << lg)) continue;
		if(R[lg][l - (1 << lg)] <= r)
			l -= (1 << lg);
	}
	if(r == n)
		return mp[A] = {l, r};
	int mt = L[0][r + 1];
	if(mt < l)
		return mp[A] = {l, r};
	l = mt;
	r ++;
	// cerr << "# " << l << ", " << r << '\n';
	return mp[A] = Solve({l, r});
}

int main(){
	ios::sync_with_stdio(0); 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++){
		int sz;
		cin >> sz;
		int v;
		for(int j = 0; j < sz; j++){
			cin >> v;
			B[i].pb(v);
		}
	}

	// cerr << "! ";
	for(int i = 1; i <= n; i++){
		L[0][i] = vis[C[i - 1]];
		for(auto x : B[i])
			vis[x] = i;
		// cerr << L[0][i] << ' ';
	}
	L[0][n + 1] = 0;
	// cerr << '\n';
	
	fill(vis, vis + N, n + 1);
	// cerr << "# ";
	for(int i = n; i >= 1; i--){
		R[0][i] = vis[C[i]];
		for(auto x : B[i])
			vis[x] = i;
		// cerr << R[0][i] << ' ';
	}
	R[0][0] = n + 1;

	// cerr << '\n';
	for(int l = 1; l < Log; l++){
		for(int i = 1; i <= n + 1; i++){
			L[l][i] = L[l - 1][i];
			if(i + (1 << (l - 1)) <= n + 1)
				L[l][i] = min(L[l][i], L[l - 1][i + (1 << (l - 1))]);
		}
	}

	for(int l = 1; l < Log; l++){
		for(int i = 0; i <= n; i++){
			R[l][i] = R[l - 1][i];
			if(i + (1 << (l - 1)) <= n)
				R[l][i] = max(R[l][i], R[l - 1][i + (1 << (l - 1))]);
		}
	}

	// auto [l,r] = Solve({3, 3});
	// cerr << "!!! [" << l << ", " << r << "]\n";
	// exit(0);
	int q;
	cin >> q;
	int x, y;

	for(int i = 0; i < q; i++){
		cin >> x >> y;
		auto [l, r] = Solve({x, x});
		// debug(l);
		// debug(r);
		cout << (l <= y && y <= r ? "YES" : "NO") << '\n';
	}
	return 0;
}

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