Submission #283095

#	Time	Username	Problem	Language	Result	Execution time	Memory
283095		maximath_1	Long Mansion (JOI17_long_mansion)	C++11	100 / 100	333 ms	52448 KiB

long_mansion

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
using namespace std;

#define ll long long
const ll mod = 1e9 + 7;

int n, q, c[500005], last_l[500005], first_r[500005], lf[500005], rg[500005];
vector<int> a[500005];
int ctr[500005];

bool check(int l, int r, int x){
	if(last_l[x] && l <= last_l[x] && last_l[x] <= r) return true;
	if(first_r[x] && l <= first_r[x] && first_r[x] <= r) return true;
	return false;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for(int i = 1; i < n; i ++)
		cin >> c[i];
	for(int sz, i = 1; i <= n; i ++){
		cin >> sz;
		for(int x, j = 0; j < sz; j ++){
			cin >> x;
			a[i].push_back(x);
		}
	}

	memset(ctr, 0, sizeof(ctr));
	for(int i = 1; i < n; i ++){
		for(int j : a[i]) ctr[j] = i;
		last_l[i] = ctr[c[i]];
	}
	memset(ctr, 0, sizeof(ctr));
	for(int i = n; i > 1; i --){
		for(int j : a[i]) ctr[j] = i;
		first_r[i - 1] = ctr[c[i - 1]];
	}

	for(int i = 1; i <= n; i ++){
		lf[i] = rg[i] = i;
		for(;;){
			if(lf[i] > 1 && check(lf[i], rg[i], lf[i] - 1)){
				rg[i] = max(rg[i], rg[lf[i] - 1]);
				lf[i] = lf[lf[i] - 1];
			}else if(rg[i] < n && check(lf[i], rg[i], rg[i])){
				rg[i] ++;
			}else break;
		}
	}

	cin >> q;
	for(int u, v, i = 0; i < q; i ++){
		cin >> u >> v;
		if(lf[u] <= v && v <= rg[u]) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}

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