제출 #1239285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239285		altern23	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	188 ms	35600 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;){
				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]){
						rg[i] = max(rg[i], rg[lf[i] - 1]);
						lf[i] = min(lf[i], lf[lf[i] - 1]);
						continue;
					}
				}
				
				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]){
						lf[i] = min(lf[i], lf[rg[i] + 1]);
						rg[i] = max(rg[i], rg[rg[i] + 1]);
						continue;
					}
				}
				
				break;
			}
		}
		
		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: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75