Submission #697102

#	Time	Username	Problem	Language	Result	Execution time	Memory
697102		amunduzbaev	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	3086 ms	172768 KiB

long_mansion

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
#define int ll

const int N = 5e5 + 5;
int c[N], b[N], last[N];
vector<int> a[N];
int l[N], r[N];
int L[N], R[N];
int mn[N][20], mx[N][20];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	for(int i=1;i<n;i++){
		cin >> c[i];
	}
	
	for(int i=1;i<=n;i++){
		cin >> b[i];
		L[i] = 1, R[i] = n;
		a[i].resize(b[i]);
		for(int j=0;j<b[i];j++){
			cin >> a[i][j];
		}
	}
	
	for(int i=0;i<N;i++) last[i] = 0;
	for(int i=1;i<=n;i++){
		for(auto x : a[i]){
			last[x] = i;
		}
		l[i] = last[c[i]];
	}
	for(int i=0;i<N;i++) last[i] = n + 1;
	for(int i=n;i>0;i--){
		r[i] = last[c[i]];
		for(auto x : a[i]){
			last[x] = i;
		}
	}
	r[0] = N, l[n] = 0;
	
	for(int i=0;i<=n;i++){
		mx[i][0] = r[i]; // r[i]
		mn[i][0] = l[i]; // l[i]
	}
	for(int j=1;j<20;j++){
		for(int i=0;i + (1 << (j - 1)) <= n;i++){
			mx[i][j] = max(mx[i][j-1], mx[i + (1 << (j - 1))][j-1]);
			mn[i][j] = min(mn[i][j-1], mn[i + (1 << (j - 1))][j-1]);
		}
	}
	
	auto get_mn = [&](int l_, int r_){
		int lg = __lg(r_ - l_ + 1);
		return min(mn[l_][lg], mn[r_ - (1 << lg) + 1][lg]);
	};
	auto get_mx = [&](int l_, int r_){
		int lg = __lg(r_ - l_ + 1);
		return max(mx[l_][lg], mx[r_ - (1 << lg) + 1][lg]);
	};
	
	for(int i=1;i<n;i++){
		{
			//~ int j = get_mn(i, r[i] - 1);
			int l_ = i + 1, r_ = r[i] - 1;
			while(l_ < r_){
				int m = (l_ + r_ + 1) >> 1;
				if(get_mn(m, r[i] - 1) <= i){
					l_ = m;
				} else {
					r_ = m - 1;
				}
			}
			int j = l_;
			if(l_ == r_ && l[j] <= i){
				for(int k=i+1;k<=j;k++){
					L[k] = max(L[k], i + 1);
				}
			}
		}
		
		{
			//~ int j = get_mx(l[i], i);
			int l_ = l[i], r_ = i - 1;
			while(l_ < r_){
				int m = (l_ + r_ ) >> 1;
				if(get_mx(l[i], m) > i){
					r_ = m;
				} else {
					l_ = m + 1;
				}
			}
			
			int j = l_;
			if(l_ == r_ && i < r[j]){
				for(int k=j+1;k<=i;k++){
					R[k] = min(R[k], i);
				}
			}
		}
	}
	
	int q; cin >> q;
	while(q--){
		int a, b; cin >> a >> b;
		if(L[a] <= b && b <= R[a]){
			cout<<"YES\n";
		} else {
			cout<<"NO\n";
		}
	}
}

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