Submission #525355

#	Time	Username	Problem	Language	Result	Execution time	Memory
525355		S2speed	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	507 ms	64012 KiB

long_mansion

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 5e5 + 16 , md = 1e9 + 7 , inf = 2e16;

ll gcd(ll a , ll b){
	if(a < b) swap(a , b);
	if(b == 0) return a;
	return gcd(b , a % b);
}

inline ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll l[maxn] , r[maxn] , a[maxn] , fl[maxn] , fr[maxn] , cnt[maxn];
vector<ll> v[maxn];

void dv(ll lx , ll rx){
	if(rx - lx == 1){
		l[lx] = lx; r[lx] = rx;
		return;
	}
	ll m = (rx + lx) >> 1;
	dv(lx , m); dv(m , rx);
	ll x , y;
	y = m;
	for(ll i = m ; i > lx ; ){
		i--;
		for(auto j : v[i]) cnt[j]++;
		while(y < rx){
			if(!cnt[a[y]]) break;
			for(auto j : v[y]) cnt[j]++;
			y++;
		}
		fr[i] = y; fl[i] = i;
	}
	for(ll i = lx ; i < m - 1 ; ){
		for(auto j : v[i]) cnt[j]--;
		i++;
		while(y > fr[i]){
			y--;
			for(auto j : v[y]) cnt[j]--;
		}
		if(cnt[a[i]]){
			fl[i] = fl[i - 1]; fr[i] = fr[i - 1];
		}
	}
	while(y > m - 1){
		y--;
		for(auto j : v[y]) cnt[j]--;
	}
//	bool f = false;
//	for(ll i = 0 ; i < 10 ; i++){
//		f |= cnt[i];
//	}
//	if(f){
//		cout<<lx<<' '<<rx<<'\n';
//	}
	for(ll i = lx ; i < m ; i++){
		if(r[i] == m){
			l[i] = fl[i]; r[i] = fr[i];
		}
	}
	x = m - 1;
	for(ll i = m - 1 ; i < rx - 1 ; ){
		i++;
		for(auto j : v[i]) cnt[j]++;
		while(x >= lx){
			if(!cnt[a[x + 1]]) break;
			for(auto j : v[x]) cnt[j]++;
			x--;
		}
		fl[i] = x + 1; fr[i] = i + 1;
	}
	for(ll i = rx - 1 ; i > m ; ){
		for(auto j : v[i]) cnt[j]--;
		i--;
		while(x < fl[i] - 1){
			x++;
			for(auto j : v[x]) cnt[j]--;
		}
		if(cnt[a[i + 1]]){
			fl[i] = fl[i + 1]; fr[i] = fr[i + 1];
		}
	}
	while(x < m){
		x++;
		for(auto j : v[x]) cnt[j]--;
	}
	for(ll i = m ; i < rx ; i++){
		if(l[i] == m){
			l[i] = fl[i]; r[i] = fr[i];
		}
	}
//	f = false;
//	for(ll i = 0 ; i < 10 ; i++){
//		f |= cnt[i];
//	}
//	if(f){
//		cout<<lx<<' '<<rx<<'\n';
//	}
	return;
}

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

	memset(cnt , 0 , sizeof(cnt));
	ll n , q;
	cin>>n;
	for(ll i = 1 ; i < n ; i++){
		cin>>a[i];
	}
	for(ll i = 0 ; i < n ; i++){
		ll k;
		cin>>k;
		for(ll j = 0 ; j < k ; j++){
			ll h;
			cin>>h;
			v[i].push_back(h);
		}
	}
	dv(0 , n);
//	wall;
//	for(ll i = 0 ; i < n ; i++){
//		cout<<l[i]<<' '<<r[i]<<'\n';
//	}
	cin>>q;
	for(ll e = 0 ; e < q ; e++){
		ll v , u;
		cin>>v>>u; v--; u--;
		if(r[v] > u && l[v] <= u){
			cout<<"YES\n";
		} else {
			cout<<"NO\n";
		}
	}
	return 0;
}

/*
5
2 3 1 3
1 3
1 2
1 1
1 3
1 2
4
1 3
3 1
4 3
2 5
*/

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