제출 #1239273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239273		altern23	Long Mansion (JOI17_long_mansion)	C++20	0 / 100	2214 ms	20612 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 5e5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;
const ld eps = 1e-6;

vector<ll> pos[MAXN + 5];
ll lf[MAXN + 5], rg[MAXN + 5];
ll c[MAXN + 5];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);		
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		for(int i = 1; i < N; i++) cin >> c[i];
		for(int i = 1; i <= N; i++){
			ll k; cin >> k;
			for(int j = 1; j <= k; j++){
				ll x; cin >> x;
				pos[x].push_back(i);
			}
		}
		
		for(int i = 1; i <= N; i++) lf[i] = rg[i] = i;
		for(int i = 1; i <= N; i++){
			for(;true;){
				ll L = lf[i], R = rg[i];
				if(lf[i] != 1){
					auto x = lower_bound(pos[c[lf[i] - 1]].begin(), pos[c[lf[i] - 1]].end(), lf[i]);
					if(x != pos[c[lf[i] - 1]].end() && (*x) <= rg[i]){
						L = min(L, lf[L - 1]);
						R = max(R, rg[L - 1]);
					}
				}
				if(rg[i] != N){
					auto x = lower_bound(pos[c[rg[i]]].begin(), pos[c[rg[i]]].end(), lf[i]);
					if(x != pos[c[rg[i]]].end() && (*x) <= rg[i]){
						L = min(L, lf[R + 1]);
						R = max(R, rg[R + 1]);
					}
				}
				
				if(L == lf[i] && R == rg[i]) break;
				lf[i] = L, rg[i] = R;
			}
		}
		
		ll Q; cin >> Q;
		for(int i = 1; i <= Q; i++){
			ll start, end; cin >> start >> end;
			cout << (lf[start] <= end && end <= rg[start] ? "YES\n" : "NO\n");
		}
	}
}

/*

*/

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